这题刚开始自己做的时候不太好理解,这里就给一下自己写的代码啦~
#include<cstdio> #include<algorithm> using namespace std; struct node { int x,y; } p[100010],q[100010]; inline bool cmp(node a,node b) { return a.x==b.x ? a.y>b.y:a.x>b.x; //机器和任务都按从大到小排序,对于任务而言,可以发现只要x1>x2,无论y大小如何,就有500*x1+2*y1>500*x2+2*y2(易证,取x1-x2=1,y1=0,y2=100),所以先按x排序,x相等再比较y } int n,m,pos,ans,s[110]; int main() { scanf("%d%d",&n,&m); for (int i=0; i<n; i++) scanf("%d%d",&p[i].x,&p[i].y); for (int i=0; i<m; i++) scanf("%d%d",&q[i].x,&q[i].y); sort(p,p+n,cmp),sort(q,q+m,cmp); long long dollars=0; for (int i=0; i<m; i++) { //枚举每个任务 while(p[pos].x>=q[i].x) s[p[pos++].y]++; //如果机器的x可行,标记一下y的位置,由于x不递增,机器的x对于后面的所有任务也都可行 for (int j=q[i].y; j<101; j++) //对于每个任务,寻找可行的最小的y if(s[j]) { s[j]--,ans++,dollars+=q[i].x*500+q[i].y*2; break; } } printf("%d %lld",ans,dollars); }
贪心讲解如有误还望各位大佬指出qwq~