首页 > 代码库 > hdu 4864 Task (贪心 技巧)
hdu 4864 Task (贪心 技巧)
题目链接
一道很有技巧的贪心题目。
题意：有n个机器，m个任务。每个机器至多能完成一个任务。对于每个机器，有一个最大运行时间xi和等级yi，
对于每个任务，也有一个运行时间xj和等级yj。只有当xi>=xj且yi>=yj的时候，机器i才能完成任务j，并获得
500*xj+2*yj金钱。问最多能完成几个任务，当出现多种情况时，输出获得金钱最多的情况。
分析：机器和任务都按照先拍x从大到小，再拍y从大到小的顺序。然后遍历任务，注意f[]数组的作用，f[]数组标
记大于当前任务时间的机器的等级个数， 由于任务都是从大到小排序了，所以接下来时间已经不是影响了，因为
已经遍历过的机器的时间都是大于 将要遍历的机器的时间的。所以只需要从 这些符合时间条件的机器里选择一个
等级最小的，以免因为等级影响后面的遍历。 为什么要按照先x排序呢，因为500 > 2*100; 为什么按照y从大到
小，因为x相等的情况下，y越大，计算的值越大。
最后注意hdu的int64;
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio> 6 #include <vector> 7 #include <algorithm> 8 #define LL long long 9 using namespace std;10 const int maxn = 100000+10;11 int n, m, f[110];12 struct node13 {14 int x, y;15 } ma[maxn], ta[maxn];16 17 bool cmp(node a, node b)18 {19 if(a.x==b.x)20 return a.y > b.y;21 return a.x > b.x;22 }23 int main()24 {25 int i, j, k, cnt;26 __int64 ans;27 while(~scanf("%d%d", &n, &m))28 {29 ans = 0; cnt = 0;30 memset(f, 0, sizeof(f));31 for(i = 0; i < n; i++)32 scanf("%d%d", &ma[i].x, &ma[i].y);33 for(i = 0; i < m; i++)34 scanf("%d%d", &ta[i].x, &ta[i].y);35 sort(ma, ma+n, cmp);36 sort(ta, ta+m, cmp);37 j = 0;38 for(i = 0; i < m; i++)39 {40 while(j < n)41 {42 if(ma[j].x >= ta[i].x)43 f[ma[j].y] ++;44 else break;45 j ++;46 }47 for(k = ta[i].y; k <= 100; k++)48 {49 if(f[k])50 {51 f[k] --;52 ans += 500*ta[i].x + 2*ta[i].y;53 cnt ++;54 break;55 }56 }57 }58 printf("%d %I64d\n", cnt, ans);59 }60 return 0;61 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。