整數集合劃分（無腦貪心，很快啊！就AC了。） (使用三種語言)

題目描述

給定一個包含 N 個正整數的集合，請你将它們劃分為兩個不相交的集合 A1 和 A2，其中 A1 包含 n1 個元素，A2 包含 n2個元素。

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

請你妥善劃分，使得 |n1−n2|盡可能小，并在此基礎上 |S1−S2|盡可能大。

輸入格式

第一行包含整數 N。

第二行包含 N個正整數。

輸出格式

再一行中輸出 |n1−n2|和 |S1−S2|，兩數之間空格隔開。

資料範圍

2 ≤ N ≤ 1 0 5 2≤N≤10^5 2≤N≤105,

保證集合中各元素以及所有元素之和小于 2 3 1 2^31 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

核心思路

題目讓兩個集合的元素個數之差最小，數值總和之差最大。 是以劃分兩個集合的思路如下：

* 對所有元素 排個序， [0,n/2] ,[n/2,n] 分别作為兩個集合。

* 受字首和的啟發： 數值總和之差 = 所有元素總和 - 兩倍的[0,n/2]區間的總和。

C++代碼

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N=100010;
int main()
{   
    vector<int>v;
	int n,s=0,x;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&x);
		v.push_back(x);
		s+=x;
	}
	
	sort(v.begin(),v.end());

     for(int i=0;i<n/2;i++)	
	{
		s-=2*v[i];
	}
	if(n%2==0)
	printf("0 %d",s);
	else
	printf("1 %d",s);
	
	return 0;
}
           

python3 代碼

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()

    diff = 0
    if n % 2 == 1: diff = 1

    print(diff, sum(a) - 2*sum(a[:n//2]))
           

java 代碼

import java.util.Scanner;
import java.util.Arrays;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] s = new int[n+1];
        int[] a = new int[n+1];
        for(int i = 1; i<= n;i++){
            s[i] =sc.nextInt();
        }
        sc.close();
        Arrays.sort(s);//排序
        for(int i = 1;i<=n;i++){
            //構造字首和數組
            a[i] = a[i-1]+s[i];
        }
        int mid = n/2;
        if(n % 2 == 1){
            System.out.print("1 "+ (a[n]-2*a[mid]));
        }else{
            System.out.print("0 "+ (a[n]-2*a[mid]));
        }
    }
}