A25817. 分配
填空题
中等
知识点
题目描述
分配
题目描述
疫情期间，社会爱心人士及单位组织为疫情捐赠了大量物资。其中有n箱口罩物资需要小蓝为2个疫情重灾区分配。每箱口罩的数量也不完全相等，且只能整箱分配。为了公平，尽量使2个疫情重灾区分得的口罩数量相等，也就是2个疫情区分得的口罩数量差值最小。
例如：n为3,3箱口罩数量分别为200、300、110,按照要求分配，2个疫情区分得的口罩数量分别为310(200+110)和300。
这时小蓝犯愁了，不知道如何才能使2个疫情重灾区分得的口罩数量尽量接近。请你编写程序帮助小蓝解决这个问题。
输入描述
第一行输入一个正整数n(n≤10),表示有n箱口罩。
第二行输入n个不完全相等的正整数(100≤每个正整数≤1000),表示每箱口罩的数量。正整数之间以一个空格隔开。
输出描述
输出两个正整数，分别表示2个重灾区分得口罩的数量，两个正整数之间一个空格隔开，且如果两个正整数不相同，需按照从大到小输出。
样例输入
3
200 300 110样例输出
310 300参考答案
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int a[20];
int n;
int sum;
int ans;
void check(int x) {
int tmp = 0;
for (int i = 0; i < n; ++i) {
if ((x >> i) & 1) {
tmp += a[i + 1];
}
}
if (abs(sum - tmp - tmp) < abs(sum - ans - ans)) {
ans = tmp;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
sum += a[i];
}
for (int i = 0; i < (1 << n); ++i) {
check(i);
}
int a1 = ans;
int a2 = sum - ans;
if (a1 < a2) {
swap(a1, a2);
}
cout << a1 << " " << a2 << endl;
return 0;
}
上一题
下一题