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;

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <cstdio>

 #include <vector>

 #include <algorithm>

 #define LL long long

 using namespace std;

 const int maxn = +;

 int n, m, f[];

 struct node

 {

     int x, y;

 } ma[maxn], ta[maxn];

 bool cmp(node a, node b)

 {

     if(a.x==b.x)

         return a.y > b.y;

     return a.x > b.x;

 }

 int main()

 {

     int i, j, k, cnt;

     __int64 ans;

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

     {

         ans = ;  cnt = ;

         memset(f, , sizeof(f));

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

             scanf("%d%d", &ma[i].x, &ma[i].y);

         for(i = ; i < m; i++)

             scanf("%d%d", &ta[i].x, &ta[i].y);

         sort(ma, ma+n, cmp);

         sort(ta, ta+m, cmp);

         j = ;

         for(i = ; i < m; i++)

         {

             while(j < n)

             {

                 if(ma[j].x >= ta[i].x)

                 f[ma[j].y] ++;

                 else break;

                 j ++;

             }

             for(k = ta[i].y; k <= ; k++)

             {

                 if(f[k])

                 {

                     f[k] --;

                     ans += *ta[i].x + *ta[i].y;

                     cnt ++;

                     break;

                 }

             }

         }

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

     }

     return ;

 }

巴特西

hdu 4864 Task (贪心技巧)

最新文章

热门文章

巴特西

hdu 4864 Task (贪心 技巧)

最新文章

热门文章

hdu 4864 Task (贪心技巧)