欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【acwing 寒假每日一题(入门组)】day18

程序员文章站 2022-07-13 08:00:56
...

题目来源:整数集合划分

题目描述

给定一个包含 N 个正整数的集合,请你将它划分为两个集合 A1 和 A2,其中 A1 包含 n1 个元素,A2 包含 n2 个元素。

集合中可以包含相同元素。

用 S1 表示集合 A1 内所有元素之和,S2 表示集合 A2 内所有元素之和。

请你妥善划分,使得 |n1−n2| 尽可能小,并在此基础上 |S1−S2| 尽可能大。

输入格式
第一行包含整数 N。

第二行包含 N 个正整数。

输出格式
再一行中输出 |n1−n2| 和 |S1−S2|,两数之间空格隔开。

数据范围
2≤N≤105,
保证集合中各元素以及所有元素之和小于 231。

输入样例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. 第一个要求元素个数只差尽可能小,就是元素对半分,偶数直接对半分就好了,奇数的话中间的元素去后面一个集合
  2. 第二个问题要求集合内元素求和之后,集合间的差尽可能地小,就是排序一下,前面一半,后面一半,然后做差

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n;
int a[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    
    sort(a,a+n);
    int s1=0,s2=0;
    for(int i=0;i<n/2;i++) s1+=a[i]; //累加集合A1
    for(int i=n/2;i<n;i++) s2+=a[i]; //累加集合A2
    cout<<n%2<<' '<<s2-s1<<endl;
    return 0;
}