整數集合劃分
題目來源：PAT甲級真題1113
時間限制：\(1000ms\) 記憶體限制：\(64mb\)
題目描述
給定一個包含 \(N\) 個正整數的集合，請你將它劃分為兩個集合 \(A_1\) 和 \(A_2\)，其中 \(A_1\) 包含 \(n_1\) 個元素，\(A_2\) 包含 \(n_2\) 個元素，
集合中可以包含相同元素，
用 \(S_1\) 表示集合 \(A_1\) 內所有元素之和，\(S_2\) 表示集合 \(A_2\) 內所有元素之和，
請你妥善劃分，使得 \(|n_1?n_2|\) 盡可能小，并在此基礎上 \(|S_1?S_2|\) 盡可能大，
輸入格式
第一行包含整數 \(N\) ，
第二行包含 \(N\) 個正整數，
輸出格式
在一行中輸出 \(|n_1?n_2|\) 和 \(|S_1?S_2|\) ，兩數之間空格隔開，
資料范圍
\(2 ≤ N ≤ 10^5\) ,
保證集合中各元素以及所有元素之和小于 \(2^{31}\) ，
樣例輸入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\) ，
元素個數為奇數的時候，分開后，元素個數差值為 \(1\) ，
然后要求子集合差值盡量大，那么一個集合里放小的元素，一個集合里放大的元素就行了，
\(N\) 為奇數的時候，不能均分，就在大元素的集合里，多放一個元素，
具體劃分兩個集合的思路如下：
- 將陣列排序后，將 \([0,n/2)\) , \([n/2,n]\) 分別作為 \(A_1\) , \(A_2\) 兩個集合，
- 數值總和之差 = 所有元素總和 - 兩倍的 \([0,n/2)\) 區間的總和，
讀入給定的陣列，邊讀入邊計算所有元素的總和，
然后減去兩倍的 \([0,n/2)\) 區間的總和，即得到最大的數值總和之差，
個數之差根據輸入的 \(N\) 來判斷，N為偶數則個數之差最小為0，否則為1，
解題代碼-Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] a = new int[n];
long s = 0;
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
s += a[i];
}
input.close();
Arrays.sort(a);
for (int i = 0; i < n / 2; i++) {
s -= 2L * a[i];
}
System.out.printf("%d %d\n", n % 2, s);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252960.html
標籤：其他