温故知新的经典贪心题目：今年暑假不AC？

情景：

“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多(more==good)的完整（entire programs）节目）

------------->

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，

分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

对于每个测试实例，输出能完整看到（watch entirely!）的电视节目的个数，每个测试实例的输出占一行。

数据样例如下：

5

我的AC代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct node

{

	int t1;//某一个电视节目的开始时间t1和结束时间t2

	int t2;

}a[105];

bool cmp(node u,node v)

{

	return (u.t2<v.t2)||(u.t2==v.t2 && u.t1>v.t1);	//以第2个字为主关键字进行升序排列.

}//set={(x,y)}以y为主关键字,以x为次关键字的升序排列。 

int main()

{

	int n;

	while(scanf("%d",&n),n)

	{

		int i;

		for(i=0;i<n;i++) scanf("%d%d",&a[i].t1,&a[i].t2);

		sort(a,a+n,cmp);

		int t=a[0].t2;

		int ans=1;

		for(i=1;i<n;i++)

		{

			if(a[i].t1>=t)

			{

				ans++;

				t=a[i].t2;

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}//贪心解决区间调度问题。

这道题背后的风景........

区间调度问题

区间调度问题：给定n项任务，每项任务的开始时间为si，结束时间为ei，只有一台机器，机器一次只能完成一项任务。想知道这台机器最多能完成多少项任务？

区间任务调度问题用贪心法求解，贪心策略是每次选取结束时间最早的任务来完成，这样就可以让机器完成尽可能多的任务(开始得晚，结束得早的话，甚好哉！)。

去看ZOJ1076 ，UVA2387：

Gene Assembly

问题传送门：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1076

基因组DNA中负责蛋白质合成的部分：parts of the genomic DNA which are responsible for the synthesis of proteins

真核生物： eukaryotes

prokaryotes：原核生物

junk DNA ：垃圾DNA

一个基因由几个编码区域（被称为外显子，exon）组成。

in the protein synthesis process：在蛋白质合成过程中

（写到这儿，我倒是稍有些疲乏了，姑且先停驻于此哦！）

巴特西

温故知新的经典贪心题目：今年暑假不AC？

最新文章

热门文章