题目链接：戳我
有 M 个任务，每个任务有两个属性 x， y， x 代表完成这个任务需要多久时间， y代表这个任务的难度系数
有 N 个机器，每个机器同样也有两个属性 x ，y，x代表这个机器每天最长工作时间， y代表这个机器最高能完成的难度系数，且一天只能工作一次，即只能完成一个任务
如果完成了一个任务， 会获得 500 * x + 2 * y 元，x，y为对应任务的x和y
问 一天内 最多可以完成 多少任务， 完成这么多任务 所获得的最大利润
1 2 ----- 1 为 机器数 N， 2为任务数 M 接下来 先是 N行，每行两个代表机器属性，同理 下面M行
100 3
100 2
100 1
（100 3） 这个机器 完成 （100 2） 这个 1 任务 所获 利润 500*100+2* = 50004
如果选择 双重 for 循环去遍历，肯定是可以的，但是会超时，所以要优化，抛弃 for 循环的冗余部分，对于每个 任务，不用遍历所有的机器 去找到合适的。
取 机器 的游标 j，j表示所有机器中能完成该任务的下限机器，每次从当前 j 开始寻找最合适的 j。
首先 把 任务 和 机器 都按照 x 从大到小排序，x相同y从大到小排序， 排序之后从头到尾遍历每一个任务对于 每一个 任务， 选择 所有 合适 的机器 中 y 最小的那个，
巧妙的代码：
//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;
const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
struct Task
{
int x, y;
}task[maxn], mac[maxn];
int n, m;
int ha[maxn];
bool cmp(Task A, Task B)
{
if(A.x == B.x) return A.y > B.y;
return A.x > B.x;
}
int main()
{
while(~scanf("%d %d", &n, &m))
{
for(int i = 0; i < n; i++)
{
scanf("%d %d", &mac[i].x, &mac[i].y);
}
for(int i = 0; i < m; i++)
{
scanf("%d %d", &task[i].x, &task[i].y);
}
sort(mac, mac+n, cmp);
sort(task, task+m, cmp);
memset(ha, 0, sizeof(ha));
int j = 0, k = 0, num = 0;
long long ans = 0;
for(int i = 0; i < m; i++)
{
while(j < n && (mac[j].x >= task[i].x)) // 找到 下限 的 机器 j
{
ha[mac[j].y]++; //把所有 x 合适的 机器的 y 记下来
j++;
}
for(k = task[i].y; k <= 100; k++)
{
if(ha[k]) //从 x 合适 的机器 中 挑选 y 也合适， 同时 y 最小
{
ans += (500 * task[i].x + 2 * task[i].y);
ha[k]--; //该机器已用，减去
num++;
break;
}
}
}
printf("%d %lld\n", num, ans);
}
return 0;
}
原文：http://www.cnblogs.com/tenlee/p/4655450.html