http://acm.hdu.edu.cn/showproblem.php?pid=4864

大致题意：有n台机器和m个任务，都有两个参数工作时间time和难度level。每个机器一天只能完成一个任务，一个任务只能被一台机器完成，每个任务完成后的利润是500*time+2*level。问在一天能完成尽量多的任务下获得的利润是多少。

思路：由上述公式知决定利润的决定性因素是时间，对任务按时间优先从大到小排序，对每一个任务先找出所有满足该任务时间的机器，然后从这些机器里选择合适且level最低的机器。也就是说机器的level从小到大排序，然后从最小的合适的level开始找合适的时间，找到一个这样合适的机器就结束。由于数目最大为100000，所以可以借助STL的set按level保存机器,查找时使用lower_bound()函数寻找下界。

#include <stdio.h>#include <iostream>#include <map>#include <set>#include <stack>#include <vector>#include <math.h>#include <string.h>#include <queue>#include <string>#include <stdlib.h>#include <algorithm>#define LL long long#define _LL __int64#define eps 1e-8#define PI acos(-1.0)using namespace std;struct node{    int time,level;    bool operator < (const struct node &tmp)const    {        if(time == tmp.time)            return level > tmp.level;        return time > tmp.time;    }}task[100010];int n,m;int cnt;_LL ans;int main(){    int x,y;    while(~scanf("%d %d",&n,&m))    {        multiset <int> mac[110];        int maxlevel = -1;        for(int i = 1; i <= n; i++)        {            scanf("%d %d",&x,&y);            mac[y].insert(x);            maxlevel = max(maxlevel,y);        }        for(int i = 1; i <= m; i++)        {            scanf("%d %d",&task[i].time,&task[i].level);        }        sort(task+1,task+1+m);        cnt = 0;        ans = 0;        for(int i = 1; i <= m; i++)        {            x = task[i].time;            y = task[i].level;            for(int j = y; j <= maxlevel; j++)            {                multiset<int>::iterator it = mac[j].lower_bound(x);                if(it == mac[j].end() || (*it) < x)                    continue;                cnt++;                ans += 500 * task[i].time + 2 * task[i].level;                mac[j].erase(it);                break;            }        }        printf("%d %I64d\n",cnt,ans);    }    return 0;}

hdu 4864 Task（贪心）