考试时，想到了一个很类似的方法，但是总是差那么点，就是这么点，需要不断的努力啊！！！
题解：
基本思想是贪心。
对于价值c=500*xi+2*yi，yi最大影响100*2<500,所以就是求xi总和最大。可以先对机器和任务的时间从大到小排序。从最大时间的任务开始，找出满足任务时间要求的所有机器，从中找出等级最低且满足任务等级要求的机器匹配。依次对任务寻找满足要求的机器。
这几乎是把标程复制了一遍，因为其中的STL用的实在巧妙而且准确，自己写的话确实搞不出来。
#include <cstdio> #include <iostream> #include <algorithm> #include <map> using namespace std; typedef long long LL; struct Task { int time; int level; }; Task task[100002],machine[100002]; bool cmp(Task a,Task b){ if(a.time==b.time) return(a.level>b.level); else return(a.time>b.time); } int main() { int n,m; while(scanf("%d%d", &n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%d%d",&machine[i].time,&machine[i].level); for(int i=0;i<m;i++) scanf("%d%d",&task[i].time,&task[i].level); sort(machine,machine+n,cmp); sort(task,task+m,cmp); int j=0,count=0;LL ans=0; map<int,int> le; for(int i=0;i<m;i++){ while(j<n&&task[i].time<=machine[j].time){ le[machine[j].level]++; j++; } map<int,int>::iterator it=le.lower_bound(task[i].level); if(it!=le.end()){ count++; ans+=task[i].time*500+task[i].level*2; int t=it->first; le[t]--; if(le[t]==0) le.erase(t); } } printf("%d %I64d ",count,ans); } return 0; }
刚才发现大神博客题解上可以不用STL ，直接扫一遍就行了，自己还是太弱了。
转：http://blog.csdn.net/a601025382s/article/details/38046927
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define LL __int64 const int maxn=1e5+10; struct node{ int x,y; }e[maxn],f[maxn]; int c[101]; int 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 i,j,k,num=0; LL ans=0; for(i=0;i<n;i++) scanf("%d%d",&e[i].x,&e[i].y); for(i=0;i<m;i++) scanf("%d%d",&f[i].x,&f[i].y); sort(e,e+n,cmp); sort(f,f+m,cmp); memset(c,0,sizeof(c)); for(i=0,j=0;i<m;i++) { while(j<n&&e[j].x>=f[i].x) { c[e[j].y]++; j++; } for(k=f[i].y;k<=100;k++) { if(c[k]) { num++; c[k]--; ans=ans+500*f[i].x+2*f[i].y; break; } } } printf("%d %I64d ",num,ans); } return 0; }