HDU 4864 Task (贪心+STL多集（二分）+邻接表存储）（杭电多校训练赛第一场1004）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4864

解题报告：有n台机器用来完成m个任务，每个任务有一个难度值和一个需要完成的时间，每台机器有一个可以工作的最长时间和一个可以完成的任务的难度的最大值，

一台机器能完成一个任务的条件是这台机器的最长工作时间和能完成任务的难度值必须都大于等于这个任务，而且一台机器最多完成一个任务，假设一个任务的时间为t,难度值为x,那么完成这个任务可以赚到的钱 money = 500 * t + 2 * x; 现在要你求最多可以完成多少个任务,而且要求能赚的钱最多。

贪心的题，难度值对能赚的钱的多少影响较小，所以将所有任务按时间从大到小排序，时间相同的按照难度值从大到小排序，然后遍历每个任务，对于每个任务，我们首先应该找到符合这个任务的时间的机器，其次机器的难度值要最小，然后还有就是尽量做时间多的任务，很显然，时间对钱的多少影响最大。

现在的问题就是怎样在最短时间内找到时间符合同时机器难度值最小的机器来完成这个任务，因为n和m的范围都是10^5，所以直接暴力明显是不行的。

我建了一个多集multiset邻接表mt来存储机器，mt[i][j]的含义是难度值为x的机器的时间是mt[i][j]，然后，用多集的原因是多集会自动对元素进行排序，而且更重要的是它有一个二分查找的函数lower_bound( x )，这个函数的功能是在这个多集里面找到最小的大于等于x的元素的位置，如果没有，则返回尾指针。有了这个就快了，可以从难度值满足的多集处开始查找，然后二分找到有没有时间上满足的。然后整个是时间复杂度是  m * 100 * log2(1000);

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef __int64 INT;
const int maxn = 100000+5;

struct node
{
    int x,y;
}task[maxn];
multiset<int> mt[105];

bool cmp(node a,node b)
{
    if(a.x == b.x)
        return a.y > b.y;
    return a.x > b.x;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int a,b;
        for(int i = 0;i <= 100;++i)
        mt[i].clear();
        for(int i = 0;i < n;++i)
        {
            scanf("%d%d",&a,&b);
            mt[b].insert(a);
        }
        for(int i = 0;i < m;++i)
        scanf("%d%d",&task[i].x,&task[i].y);
        sort(task,task+m,cmp);
        INT num = 0,tot = 0;
        for(int i = 0;i < m;++i)
        {
            int p = -1;
            multiset<int>::iterator iter;
            for(int j = task[i].y;j <= 100;++j)    //mt[j]集中数的含义是所有难度为j的机器的时间
            {
                iter = mt[j].lower_bound(task[i].x);  //lower_bound（）用二分查找找到最小的大于或等于task[i].x的数的位置
                if(iter != mt[j].end())
                {
                    p = j;
                    break;
                }
            }
            if(p != -1)
            {
                num++;
                tot += (500 * task[i].x + 2 * task[i].y);
                mt[p].erase(iter);
            }
        }
        printf("%I64d %I64d
",num,tot);
    }
    return 0;
}