【PAT甲级 - C++题解】1113 Integer Set Partition

简介: 【PAT甲级 - C++题解】1113 Integer Set Partition

1113 Integer Set Partition


Given a set of N (>1) positive integers, you are supposed to partition them into two disjoint sets A1 and A2 of n1 and n2 numbers, respectively. Let S1 and S2 denote the sums of all the numbers in A1 and A2, respectively. You are supposed to make the partition so that ∣n1−n2∣ is minimized first, and then ∣S1−S2∣ is maximized.


Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤105), and then N positive integers follow in the next line, separated by spaces. It is guaranteed that all the integers and their sum are less than 231.


Output Specification:

For each case, print in a line two numbers: ∣n1−n2∣ and ∣S1−S2∣, separated by exactly one space.


Sample Input 1:

10
23 8 10 99 46 2333 46 1 666 555

Sample Output 1:

0 3611

Sample Input 2:

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

Sample Output 2:

1 9359


题意

给定 n 个数,将这 n 个数划分成两个集合 A1 和 A2 ,其中 A1 包含 n1 个数且这些数之和为 s1 ,A2 包含 n2 个数且这些数之和为 s2 。


现在需要我们使 |n2-n1| 的值尽可能的小,且 |s2-s1| 的值尽可能的大。


思路

直接上结论,我们只要将数组先排个序,然后尽可能均匀的分成两部分,所以 |n2-n1| 的值只可能为 0 或 1 ,且左半部分的值都是小于右半部分的,这样就能使 |s2-s1| 的值最大。


代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int w[N];
int n;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)    cin >> w[i];
    //进行排序
    sort(w, w + n);
    //计算两部分数值的和
    int s1 = 0, s2 = 0;
    for (int i = 0; i < n / 2; i++)  s1 += w[i];
    for (int i = n / 2; i < n; i++)  s2 += w[i];
    //输出结果
    cout << n % 2 << " " << s2 - s1 << endl;
    return 0;
}
目录
打赏
0
0
0
0
37
分享
相关文章
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对,每个键唯一;而`set`存储唯一元素,不包含值。两者均基于红黑树实现,支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口,并简要对比了`map`与`set`的主要差异。此外,还介绍了允许重复元素的`multiset`和`multimap`。
62 3
【C++】map、set基本用法
【C++】unordered_map(set)
C++中的`unordered`容器(如`std::unordered_set`、`std::unordered_map`)基于哈希表实现,提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中,每个桶可存储一个或多个元素,以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列,以及迭代器。哈希函数用于计算元素的哈希值,冲突通过开链法解决,负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1),但在冲突较多时可能退化为O(n)。
37 5
【C++】set模拟实现
C++中的`set`是STL提供的一种关联容器,用于存储唯一元素并自动按特定顺序(默认升序)排序。其内部通过红黑树实现,保证了高效的插入、删除和查找操作,时间复杂度均为O(log n)。`set`支持迭代器遍历,提供了良好的数据访问接口。
51 3
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
91 0
|
7月前
|
【C++】map和set封装
【C++】map和set封装
54 2
|
7月前
|
【C++】map和set深度讲解(下)
【C++】map和set深度讲解(下)
79 2
【C++】map和set深度讲解(上)
【C++】map和set深度讲解(上)
62 2
|
8月前
|
C++之set/multiset容器
C++之set/multiset容器
【C++航海王:追寻罗杰的编程之路】set|map|multiset|multimap简单介绍
【C++航海王:追寻罗杰的编程之路】set|map|multiset|multimap简单介绍
64 0
【C++航海王:追寻罗杰的编程之路】set|map|multiset|multimap简单介绍