杭电oj 2037
题目链接
Problem Description
“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”
确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）
Input
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。
Output
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。
Sample Input
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
Sample Output
5
Author
lcy
c版：
#include "stdio.h"
int a[100],b[100];
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
if(n<=0)continue;
for(i=0;i<n;i++)
scanf("%d %d",&a[i],&b[i]);
int count=1;
int x;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(b[i]>b[j])
{
x=b[i];
b[i]=b[j];
b[j]=x;
x=a[i];
a[i]=a[j];
a[j]=x;
}
int y=b[0];
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(y<=a[j])
{
i=j;//下一次大循环将由j开始找写一个节目开始时间
y=b[j];//对应其结束时间
count++;
}
printf("%d\n",count);
}
return 0;
}
这道题一看有点摸不着头绪，题目要求输出能完整看到的电视节目的个数，但是一开始想的是完整看到的节目，看一个完整的也是“完整看完”，看两个完整的也是“完整看完”，这样的题目没啥意思，后来觉得应该是“最多能完整看完几个节目”的意思，因此如果要让节目个数尽量多，那只能缩短每个看的节目的时间。那可以这样考虑，我先选择一个早点结束的节目，再以这个时间点选择相邻时间开始的节目，再以结束时间作为下一个节目的开始时间，以此类推。这个时候就涉及到要将每个结束时间排序，毕竟结束时间较早的节目时长也会相对较短吧。
前几篇文章提过，c++中sort()函数可以为c语言中排序问题省略至少5 6条语句，于是，初学c++的我打算练一练手，但是目前只会改一点点c版里的代码啊啊啊，初学者很生涩莫见怪……
c++版：
#include<iostream>
#include<algorithm>
using namespace std;
struct TV
{
int s;
int e;
};
bool cmp(TV tv1,TV tv2) //sort()的第三个参数：从小到大排列
{
return tv1.e<tv2.e;
}
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
if(n<=0)continue;
TV *tv=new TV[n];
for(i=0;i<n;i++)
cin>>tv[i].s>>tv[i].e; //scanf("%d %d",&a[i],&b[i]);
int count=1;
int x;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
sort(tv,tv+n,cmp);
/*if(b[i]>b[j])
{
x=b[i];
b[i]=b[j];
b[j]=x;
x=a[i];
a[i]=a[j];
a[j]=x;
}*/
int y=tv[0].e;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(y<=tv[j].s)
{
i=j;//下一次大循环将由j开始找写一个节目开始时间
y=tv[j].e;//对应其结束时间
count++;
}
cout<<count<<endl;//printf("%d\n",count);
}
return 0;
}
