考察:贪心
错误思路:
为了让利益最大,任务时间首先要尽可能大,在时间相同情况下,等级要尽可能大.采取双指针的类似思想,排序后从尾到头遍历,从m~1找到所能完成的任务数,如果机器时间或者等级＜当前任务就continue
此思路错在如果最大时间的机器等级非常低,而完成任务的机器都排在后面就会一直continue,使得答案为0.
正确思路:
同样是从尾到头遍历,但是只比较时间,找到第一个不能时间完成的机器,统计它前面能够完成的等级出现次数,在for找最小等级能完成的机器即可.如果后面出现的任务时间与之前相同,直接遍历之前统计的次数即可,如果＜就继续找第一个时间上不能完成任务的机器.
一次只考虑一个条件,这样就不会被等级卡住.
贪心思路:找到与任务要求相差不多的机器.
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 const int N = 100010,M = 110; 7 typedef pair<int,int> PII; 8 typedef long long LL; 9 PII p[N],task[N]; 10 int counts[M]; 11 int main() 12 { 13 int m,n; 14 while(scanf("%d%d",&n,&m)!=EOF) 15 { 16 memset(counts,0,sizeof counts); 17 LL ans = 0; int cnt = 0; 18 for(int i=1;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second); 19 for(int i=1;i<=m;i++) scanf("%d%d",&task[i].first,&task[i].second); 20 sort(p+1,p+n+1); 21 sort(task+1,task+m+1); 22 for(int i=m,j=n;i>=1;i--) 23 {//如果第一个时间都不够,后面的时间一定不够 24 while(j&&task[i].first<=p[j].first) 25 { 26 counts[p[j].second]++; 27 j--; 28 }//无需判断条件,当没有进入while循环说明j比i时间少,上次统计的一定可以做 29 for(int t=task[i].second;t<=100;t++) 30 { 31 if(counts[t]) 32 { 33 cnt++,ans+=task[i].second*2LL+task[i].first*500LL; 34 counts[t]--; 35 break; 36 } 37 } 38 } 39 printf("%d %lld\n",cnt,ans); 40 } 41 return 0; 42 }
原文：https://www.cnblogs.com/newblg/p/14427829.html