pid=4864">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;

}