这是福州赛区网络赛最后一个题,听说可以用动态规划做。但是我感觉用贪心也可以做(很久以前做的,现在是想记录在博客上)。于是就思考用贪心怎么做。
题目意思非常简单,就是一个噬菌体可以产生新的噬菌体,这些噬菌体可以感染细胞,感染每个细胞的需要的噬菌体数量和journey 所需时间不一样。问感染所有细胞至少需要多少时间?
大概思路:贪心必定要排序,我定义了一个结构体数组(num,time),按时间从大到小排序。变量sum 动态记录所需总时间,remain可以空闲以做他用的时间。详细说明在代码注释中。
代码:
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int num,time;// 数量 和 所需时间
} phage;
phage a[100001];
int cmp(const void *a,const void *b)//按时间从大到小排序
{
return ((phage *)b)->time - ((phage *)a)->time;
}
int main()
{
int T,cell,i,j,k = 1,next;
scanf("%d",&T);
getchar();
do
{
int sum = 0,remain;
scanf("%d",&cell);
for(i = 0 ; i != cell ; ++i)
scanf("%d%d",&a[i].num,&a[i].time);
qsort(a,cell,sizeof(a[0]),cmp);
sum = a[0].time + a[0].num ;// sum 动态记录至少需要的时间
remain = a[0].time;//the time of journey ,表示可以空下来生产phage 的时间
for(i = 1 ; i < cell ; ++i)
{
next = a[i].num + a[i].time;//感染下一个细胞所需时间
if( next < remain )//remain 够用
{
remain -= a[i].num;//用掉一部分remain
}
else //remain 不够用了
{
sum +=(next - remain);// sum 就要增加
remain = a[i].time;//更新remain
}
}
printf("Case %d: %d\n",k++,sum);
}while(--T);
//system("pause");
return 0;
}