HDU - 4221 贪心

题意：

你有n个任务，每一个任务有一个完成所需时间AI，和一个截止时间BI。时间从0开始，如果完成任务的时间（设这个时间为ans）大于BI那么就会收到ans-BI的惩罚，问你完成所有这些任务你会收到的最大惩罚是多少。让你求这个惩罚的最小值

题解：

刚开始以为让找的是完成每一个任务所受惩罚的和的最小值。最后才发现题意读错了。。。

假设有两个任务，一个任务为a1,b1,另一个任务是a2,b2.且b2>b1，起始时间为tmp

那么如果先完成第一个任务耗时最大值为max(tmp+a1+a2-b2,tmp+a1-d1)

如果先完成第二个任务耗时最大值为max(tmp+a2+a1-d1,tmp+a2-d2)>max(tmp+a1+a2-b2,tmp+a1-d1)

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<vector>

 7 #include<queue>

 8 #include<stack>

 9 #include<map>

10 using namespace std;

11 typedef long long LL;

12 const int maxn=505;

13 //const LL MAX=1e15;

14 const int INF=0x3f3f3f3f;

15 const double eps=1e-8;

16 const double PI=3.1415926;

17 const int mod = 1e9+7;

18 const int MAX=100000+10;

19 struct Time

20 {

21     LL s,e;

22 } T[MAX];

23 bool cmp(Time a,Time b)

24 {

25     return a.e<b.e;

26 }

27 int main()

28 {

29     LL cas,i,n,tag=1;

30     LL ans;

31     cin>>cas;

32     while(cas--)

33     {

34         scanf("%I64d",&n);

35         for(i=0; i<n; i++)

36             scanf("%I64d%I64d",&T[i].s,&T[i].e);

37

38         sort(T,T+n,cmp);

39         ans=0;

40         LL tmp=0;

41         for(i=0; i<n; i++)

42         {

43             tmp+=T[i].s;

44             if(tmp-T[i].e>ans)

45                 ans=tmp-T[i].e;

46         }

47         printf("Case %I64d: %I64d\n",tag++,ans);

48     }

49     return 0;

50 }

巴特西

HDU - 4221 贪心

最新文章

热门文章