题目描述
给定一个包含 N 个正整数的集合,请你将它们划分为两个不相交的集合 A1 和 A2,其中 A1 包含 n1 个元素,A2 包含 n2 个元素。
用 S1 表示集合 A1 内所有元素之和,S2 表示集合 A2 内所有元素之和。
请你妥善划分,使得 |n1−n2| 尽可能小,并在此基础上 |S1−S2| 尽可能大。
样例
输入样例1:
10
23 8 10 99 46 2333 46 1 666 555
输出样例1:
0 3611
输入样例2:
13
110 79 218 69 3721 100 29 135 2 6 13 5188 85
输出样例2:
1 9359
算法1
贪心 + 排序 + 双指针
时间复杂度 O(nlogn)
根据题意,我们得到:题目要我们把给定的整数划分为两个集合,并且使得这两个集合所含的数字个数之差最小,并且集合的数字总和差最大。
于是我们有如下的贪心思路:
先将数组排序,两个指针分别指向当前数组的最大值和最小值,每一次取出当前的最小值放到其中一个集合,取出当前的最大值放到另一个集合,这样一来当两个指针相遇的时候我们就放置完了所有的数,并且现在两个集合是满足题意的。
另外,如果两个指针最后相等,说明数字有奇数个,那么最后两集合的数字个数差就是1,若不相等则是0。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int nums[N];
int n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> nums[i];
sort(nums + 1, nums + n + 1);
int sum_1 = 0, sum_2 = 0;
int l = 1, r = n;
while (l < r)
{
sum_1 += nums[l];
sum_2 += nums[r];
l ++ , r -- ;
}
int cnt = 0; // 两集合的数字个数差
if (l == r)
{
if (sum_1 > sum_2) sum_1 += nums[l];
else sum_2 += nums[l];
cnt = 1;
}
cout << cnt << ' ' << abs(sum_1 - sum_2) << endl;
return 0;
}
有点麻烦了,可以直接从中间断开来求QAQ
是小姐姐咩?😏
😏
— — 应该不存在小姐姐的。。打扰了打扰了
小姐姐的话去找P云呐,不仅是小姐姐还是大佬~