营销网站建设资料,网站怎样做优化,嘉兴网站制作策划,保定建站方案题意#xff1a;n台机器工作时间为ai,等级bi,m个任务需要时间ai#xff0c;等级bi,一台机器只能完成一个任务#xff0c;完成一个任务收益为500*ai2*bi,求最大收益#xff1b;(n,m100000) 思路#xff1a;先从大到小排时间#xff0c;再从大到小排等级#xff0c;借…题意n台机器工作时间为ai,等级bi,m个任务需要时间ai等级bi,一台机器只能完成一个任务完成一个任务收益为500*ai2*bi,求最大收益(n,m100000) 思路先从大到小排时间再从大到小排等级借助等级数不超过100的条件使用贪心以确保不超时 对于每个任务在满足工作时间大于所需时间的条件下统计对应等级的机器数量 当前统计的等级中的机器一定能完成后面的任务很巧妙的贪心 本题也可使用高斯消元实现http://blog.csdn.net/a601025382s/article/details/38047905 高斯消元入门http://blog.csdn.net/tsaid/article/details/7329301 #includecstdio
#includecstring
#includealgorithm
using namespace std;
int t,n,m;
struct node
{int x,y;
}N[500010],M[500010];
int cmp(node a,node b)
{if(a.xb.x) return a.yb.y;return a.xb.x;
}
int rk[500100];
__int64 sum;
int main()
{int i,j,k,cnt;while(scanf(%d%d,n,m)!EOF){sum0;cnt0;memset(rk,0,sizeof(rk));for(i0;in;i)scanf(%d%d,M[i].x,M[i].y);sort(M,Mn,cmp);for(i0;im;i)scanf(%d%d,N[i].x,N[i].y);sort(N,Nm,cmp);for(i0,j0;im;i){while(jnM[j].xN[i].x){rk[M[j].y];j;}for(kN[i].y;k100;k){if(rk[k]){rk[k]--;cnt;sum(500*N[i].x2*N[i].y);break;}}}printf(%d %I64d\n,cnt,sum);}return 0;
} 转载于:https://www.cnblogs.com/dashuzhilin/p/4655171.html
