PAT甲级考试1113科目有哪些？

本文共计594个文字，预计阅读时间需要3分钟。

题目：1113. 整数集合划分（25分）时间限制：150 ms内存限制：65536 kB代码长度限制：16000 B题目描述：给定一个包含N（1≤N≤50000）个正整数的集合，你需要将它们划分为两个互斥的子集。

1113. Integer Set Partition (25)

时间限制

150 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

Given a set of N (> 1) positive integers, you are supposed to partition them into two disjoint sets A₁and A₂of n₁and n₂numbers, respectively. Let S₁and S₂denote the sums of all the numbers in A₁and A₂, respectively. You are supposed to make the partition so that |n₁- n₂| is minimized first, and then |S₁- S₂| is maximized.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2 <= N <= 10⁵), 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 2³¹.

Output Specification:

For each case, print in a line two numbers: |n₁- n₂| and |S₁- S₂|, 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

#include<cstdio>
#include<algorithm>
using namespace std;
int a[100000];
int main()
{
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
scanf("%d", &a[i]);
}
sort(a, a + N);
int sum1 = 0, sum2 = 0;
for (int i = 0; i < N; i++)
{
if (i <= N/2-1)
sum1 += a[i];
else
sum2 += a[i];
}
if (N % 2 == 0)
{
printf("%d %d\n", 0, sum2 - sum1);
}
else
printf("%d %d\n", 1, sum2 - sum1);
return 0;
}