A28391. 平均分配
填空题
困难
知识点
题目描述
平均分配
题目描述
小A有2n件物品，小B和小C想从小A手上买走这些物品。对于第i件物品，小B会以bi的价格购买，而小C会以Ci的价格购买。为了平均分配这2n件物品，小A决定小B和小C各自只能买走恰好n件物品。你能帮小A求出他卖出这2n件物品所能获得的最大收入吗？
输入格式
第一行，一个正整数n。
第二行，2n个整数b1,b2,...,b2n 。
第三行，2n个整数c1,c2,...,c2n 。
输出格式
一行，一个整数，表示答案。
样例
输入样例 1
3
1 3 5 6 8 10
2 4 6 7 9 11输出样例 1
36输入样例 2
2
6 7 9 9
1 2 10 12输出样例 2
35数据范围
对于20% 的测试点，保证1≤n≤8 。
对于另外20% 的测试点，保证0≤bi≤1，0≤ci≤1。
对于所有测试点，保证1≤n≤105 ，0≤bi≤109，0≤ci≤109 。
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
long long b[N], c[N], d[N];
long long ans;
int main() {
scanf("%d", &n);
assert(1 <= n && n <= 1e5);
for (int i = 1; i <= 2 * n; i++)
scanf("%lld", &b[i]), assert(0 <= b[i] && b[i] <= 1e9);
for (int i = 1; i <= 2 * n; i++)
scanf("%lld", &c[i]), assert(0 <= c[i] && c[i] <= 1e9);
for (int i = 1; i <= 2 * n; i++) {
ans += b[i];
d[i] = c[i] - b[i];
}
sort(d + 1, d + 2 * n + 1);
for (int i = n + 1; i <= 2 * n; i++)
ans += d[i];
printf("%lld\n", ans);
return 0;
}
上一题
下一题