hdoj4864 Task （贪心）

港控/mmm° 2022-09-20 15:24 32阅读 0赞

题目来源：

2014 Multi-University Training Contest 1--by FZU

题意：有N个机器和m个工作，机器和工作都有一个时间xi和价值yi，一个工作只有满足xi和yi都小于机器的才能在这个机器上做，一个机器最多能做一个工作，做一个工作获得的钱是工作的xi\*500+yi\*2，最多完成多少任务，最多有多个的话输出钱最多的。怎样安排？

分析：贪心题目，比赛的时候想到贪心，是给机器选工作，工作时间跟小于机器最接近的，然后还有一个价值yi，不好贪心。

中间又想到把他们的值放在一个矩阵中贪心，转化为在一个子矩阵中求结果，这个思想也是很好的，但是大前提没有考虑正确，其实是给工作选机器。为什么呢？

因为题目求让完成的任务最多，所以可以把工作和机器都按时间从大到小，然后价值从大到小，然后给每个工作找机器，首先所有的工作时间比当前任务的工作时间大的都可以选，我们贪心选择其中价值最小的满足条件的一个机器，把大的留给后面的。这样思路就没有错了、

然后是处理，如果直接写的话接近O（n^2),必超时，开始想到的优先队列，但是优先队列返回的是最小的，我们要的是首先要满足大于当前任务价值，所以不行，然后可以用vector，也可以直接用一个数组处理，因为时间都是满足条件的，只要贪心选择一个最优的价值，所以可以用一个哈希数组，很简单的小处理了。

代码：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    const int N = 101000;
    struct Node
    {
        int xi,yi;
    };
    
    Node mac[N];
    Node pro[N];
    int cmp(Node a,Node b)
    {
        if(a.xi!=b.xi)
            return a.xi>b.xi;
        if(a.yi!=b.yi)
            return a.yi>b.yi;
    }
    int flag[120];
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=0;i<n;i++)
                scanf("%d%d",&mac[i].xi,&mac[i].yi);
            for(int i=0;i<m;i++)
                scanf("%d%d",&pro[i].xi,&pro[i].yi);
            sort(mac,mac+n,cmp);
            sort(pro,pro+m,cmp);
            memset(flag,0,sizeof(flag));
            int tmp=-1;
            long long ans=0,count=0;
            for(int i=0,j=0;i<m;i++)
            {
                while(j<n&&mac[j].xi>=pro[i].xi)
                {
                    flag[mac[j].yi]++;
                    j++;
                }
                for(int k=pro[i].yi;k<=100;k++)
                {
                    if(flag[k])
                    {
                        flag[k]--;
                        ans++;
                        count+=(pro[i].xi*500+pro[i].yi*2);
                        break;
                    }
                }
            }
            printf("%I64d %I64d\n",ans,count);
        }
        return 0;
    }
    /*
    1 2
    100 3
    100 2
    100 1
    2 2
    100 3
    200 1
    100 2
    100 1
    */