引言
题目链接:https://codeforces.com/contest/1914/problem/E2
思路
假设有数组 \(a_1,a_2, \cdots a_n\) 和数组 \(b_1,b_2, \cdots b_n\) 分别表示 \(Alice\) 和 \(Bob\) 的弹珠数。
假设有如下的数据:
a1 a2
b1 b2
那么 \(Alice\) 选择 a1 和 a2 所得分数分别为:
\(a1 - 1 - (b2 - 1) = a1 - b2\)
\(a2 - 1 - (b1 - 1) = a2 - b1\)
所以若选择 \(a1\) 则应该有:
\(a1 - b2 > a2 - b1\)
整理可得:
\(a1 + b1 > a2 + b2\)
所以对于该题,可以把 \(a_i + b_i\) 取得,之后不停取大的即可得到答案。
代码
#include <bits/stdc++.h>
#define ll long long
#define N 1000000
struct Node{
int x,y;
bool operator < (const Node &p) const {
return (x + y) > (p.x + p.y);
}
}node[N];
void solve() {
int n;
std::cin >> n;
for (int i = 1 ; i <=n ; i ++ ) std::cin >> node[i].x;
for (int i = 1 ; i <=n ; i ++) std::cin >> node[i].y;
std::sort(node+1,node+1+n);
ll res = 0;
for (int i = 1 ; i <= n ; i ++ ) {
if(i % 2) {
res += node[i].x - 1;
} else {
res -= node[i].y - 1;
}
}
std::cout << res << "\n";
}
int main()
{
int t;
std::cin >>t;
while(t -- ) {
solve();
}
return 0;
}