AcWing 1603. 整数集合划分(JAVA)
原题链接
简单
作者:
crayon不小心
,
2021-01-26 16:06:35
,
所有人可见
,
阅读 401
1.此题中,理解|n1-n2|足够小,此时|S1-S2|足够大的此种情况下,就是从小大小排列数组,取中位数(无需考虑奇数or偶数)。
2.再分配数组后向前逐个考究新数组之间的绝对值相对于之前是否增大,若不增大,舍去,若一直增大,取之。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int [] s = new int[N];
for (int i = 0; i < N; i++) {
s[i] = sc.nextInt();
}
Arrays.sort(s);
int m = s.length/2;
int [] a;
int [] b;
a = Arrays.stream(s,0,m).toArray(); //The index m is not in array a but in array b, the size of a is m
b = Arrays.stream(s,m,s.length).toArray();
int res_1 = 0, res_2 = 0;
for (int i : a) res_1 += i;
for (int j : b) res_2 += j;
int cnt = Math.abs(res_1-res_2);
int k = Math.abs(a.length-b.length);
for (int i = a.length - 1; i >= 0; i--) {
res_2 += s[i];
res_1 -= s[i];
int res = Math.max(cnt,Math.abs(res_1-res_2));
if (res>cnt)
{
System.out.println(k + " " + cnt);
break;
}
k++;
}
}
}