广西工程建设质量管理协会网站,平台网站建设后台源码,哪个网站可以免费学编程,中国电子信息网HDU-7323 2023“钉耙编程”杭电多校赛#xff08;3#xff09;a-b Problem
题目大意
小 A A A和小 B B B在玩游戏。有 n n n块石头#xff0c;小 A A A和小 B B B轮流捡#xff0c;小 A A A先捡。每人每次只能捡一块石头#xff0c;直到所有的石头都被捡完。
每块石头都…HDU-7323 2023“钉耙编程”杭电多校赛3a-b Problem
题目大意
小 A A A和小 B B B在玩游戏。有 n n n块石头小 A A A和小 B B B轮流捡小 A A A先捡。每人每次只能捡一块石头直到所有的石头都被捡完。
每块石头都有两个属性 a i a_i ai和 b i b_i bi。当小 A A A捡到一块石头时他得到 a i a_i ai分当小 B B B捡到一块石头时他得到 b i b_i bi分。
他们的总得分为他们捡石头时得分的总和。
两名玩家都希望自己的分数比另一位玩家更高且都采用最优策略求小 A A A的得分减去小 B B B的得分后的值。
有 T T T组数据。 1 ≤ T ≤ 20 , 1 ≤ n ≤ 1 0 5 1\leq T\leq 20,1\leq n\leq 10^5 1≤T≤20,1≤n≤105 题解
我们可以将问题看做在一开始时所有石头都在小 B B B手中每次轮到小 A A A时小 A A A可以取走小 B B B手中的一个石头轮到小 B B B时小 B B B可以藏起一块石头不让小 A A A拿。每次小 A A A拿石头时两个玩家的分数差就增加了 a i b i a_ib_i aibi所以小 A A A会优先拿 a i b i a_ib_i aibi最大的石头小 B B B也会优先藏 a i b i a_ib_i aibi最大的石头只需将所有石头按 a i b i a_ib_i aibi从大到小排序再让小 A A A和小 B B B从前往后轮流取即可。
code
#includebits/stdc.h
using namespace std;
int T,n;
long long ans;
struct node{int a,b,c;
}w[100005];
bool cmp(node ax,node bx){return ax.cbx.c;
}
int main()
{scanf(%d,T);while(T--){scanf(%d,n);ans0;for(int i1;in;i){scanf(%d%d,w[i].a,w[i].b);w[i].cw[i].aw[i].b;}sort(w1,wn1,cmp);for(int i1;in;i2){answ[i].a;if(i1n) ans-w[i1].b;}printf(%lld\n,ans);}return 0;
}
