【PAT】1113. Integer Set Partition (25)【字符串处理】

本文主要是介绍【PAT】1113. Integer Set Partition (25)【字符串处理】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

Given a set of N (>1) positive integers, you are supposed to partition them into two disjoint sets A_​1 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_​1−n₂∣ is minimized first, and then ∣S_​1−S₂∣ is maximized.

翻译：给定有N(>1)个正整数的集合，你需要将它们分成两个不重合的集合A₁和A₂，分别有n₁ 和 n₂个数字。让S₁ 和S₂分别表示A₁ 和A₂中的元素之和，你需要做出分类，使∣n_​1−n₂∣最小，∣S_​1−S₂∣最大。

Input Specification:

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

翻译：每个输入文件包含一组测试数据。对于每组输入数据，第一行包括一个正整数N(2≤N≤10^​5​)，接下来一行包括N个正整数，用空格隔开。数据保证所有正整数和它们的和不超过 2³¹。

Output Specification:

For each case, print in a line two numbers: ∣n₁−n₂∣ and ∣S₁−S₂∣, separated by exactly one space.

翻译：对于每组输入数据，输出一行两个数字：∣n₁−n₂∣ 和 ∣S₁−S₂∣,中间用空格隔开。

---

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

---

解题思路

这道题数据设计的有些问题，直接调用sort试了一下，O(nlogn)的复杂度没有超时，就不想了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#define INF 99999999
#define bug puts("Hello\n")
using namespace std;
int N;
int num[100010];
int main(){scanf("%d",&N);for(int i=0;i<N;i++)scanf("%d",&num[i]);sort(num,num+N);int sum1=0,sum2=0;for(int i=0;i<N/2;i++){sum1+=num[i];}for(int i=N/2;i<N;i++){sum2+=num[i];}printf("%d %d\n",N%2,sum2-sum1);return 0;
}

这篇关于【PAT】1113. Integer Set Partition (25)【字符串处理】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---