1、看电视
题目描述 暑假到了，小明终于可以开心的看电视了。但是小明喜欢的节目太多了，他希望尽量多的看到完整的节目。 现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？ 输入 输入包含多组测试数据。每组输入的第一行是一个整数n（n<=100），表示小明喜欢的节目的总数。 接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。 当n=0时，输入结束。
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0输出 对于每组输入，输出能完整看到的电视节目的个数。
5分析：这里值得注意的是，一个电视节目结束的同时可以看另一个节目 贪心策略：在可选的节目中，每次先看结束时间早的。这就需要对各个节目结束时间进行从小到大的排序。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxN=105;
typedef pair<int,int>PII;
void solve(PII t[],int n)
{
sort(t,t+n);//排序
int ans=0,endT=0;//endT是上一个已选节目的结束时间
for(int i=0;i<n;i++)
{
if(endT<=t[i].second)//该节目的开始时间等于或晚于上一个已选节目的结束时间
{
ans++;
endT=t[i].first;
}
}
printf("%d\n",ans);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n)
{
int S[maxN],T[maxN];
for(int i=0;i<n;i++)
{
scanf("%d%d",&S[i],&T[i]);
}
//使用pair类型存储开始、结束时间
//first存储结束时间，因为后续要排序，而排序默认按first从小到大排序
PII time[maxN];
for(int i=0;i<n;i++)
{
time[i].first=T[i];
time[i].second=S[i];
}
solve(time,n);
}
return 0;
}2、找零钱
题目描述 小智去超市买东西，买了不超过一百块的东西。收银员想尽量用少的纸币来找钱。 纸币面额分为50 20 10 5 1 五种。请在知道要找多少钱n给小明的情况下，输出纸币数量最少的方案。 1<=n<=99; 输入 有多组数据 1<=n<=99; 输出 对于每种数量不为0的纸币，输出他们的面值*数量，再加起来输出
25
32
20*1+5*1
20*1+10*1+1*2贪心策略：优先用面值大的支付
#include<iostream>
#include<cstring>
using namespace std;
int n;
int value[]={50,20,10,5,1};//面值
int cnt[5];//每种钱的张数
void solve()
{
for(int i=0;i<5;i++)
{
int t=n/value[i];
cnt[i]=t;
n-=t*value[i];
if(n==0)break;
}
bool flag=false;
for(int i=0;i<5;i++)
{
if(cnt[i]!=0)
{
if(flag)printf("+");//控制输出第一个前没有+
printf("%d*%d",value[i],cnt[i]);
flag=true;
}
}
printf("\n");
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(cnt,0,sizeof(cnt));
solve();
}
return 0;
}3、Repair the Wall
题目描述
Long time ago , Kitty lived in a small village. The air was fresh and the scenery was very beautiful. The only thing that troubled her is the typhoon.
When the typhoon came, everything is terrible. It kept blowing and raining for a long time. And what made the situation worse was that all of Kitty's walls were made of wood.
One day, Kitty found that there was a crack in the wall. The shape of the crack is
a rectangle with the size of 1×L (in inch). Luckly Kitty got N blocks and a saw(锯子) from her neighbors.
The shape of the blocks were rectangle too, and the width of all blocks were 1 inch. So, with the help of saw, Kitty could cut down some of the blocks(of course she could use it directly without cutting) and put them in the crack, and the wall may be repaired perfectly, without any gap.
Now, Kitty knew the size of each blocks, and wanted to use as fewer as possible of the blocks to repair the wall, could you help her ?
输入
The problem contains many test cases, please process to the end of file( EOF ).
Each test case contains two lines.
In the first line, there are two integers L(0<L<1000000000) and N(0<=N<600) which
mentioned above.
In the second line, there are N positive integers. The ith integer Ai(0<Ai<1000000000 ) means that the ith block has the size of 1×Ai (in inch).
输出
For each test case , print an integer which represents the minimal number of blocks are needed.
If Kitty could not repair the wall, just print "impossible" instead.#include<iostream>
#include<algorithm>
using namespace std;
const int maxN=605;
int L,n;
int main()
{
while(scanf("%d%d",&L,&n)!=EOF)
{
int a[maxN];
int sum=0;
bool flag=false;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(int i=n-1;i>=0;i--)
{
sum+=a[i];
if(sum>=L)
{
flag=true;
printf("%d\n",n-i);
break;
}
}
if(!flag)printf("impossible\n");
}
return 0;
}