PAT 1113 C++

PAT 1113 C++

1.题意

给出一系列N 个正整数，你需要将其分成 n1,n2 两个集合。其中，S1,S2 分别代表的是两个集合中的数据，现在求出使得 |n1-n2| 最小，但是|S1-S2|最大的分配。

2.分析

• step 1：先排序
• step 2：再对前后两部分求和

3.测试用例

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

4. 代码

#include<cstdio>
#include<algorithm>
using namespace std; 

int cmp(int a,int b){
	return a < b;
}

int main(){
	int N ;
	scanf("%d",&N);
	//printf("N = %d\n",N);
	int i;
	int array[N]; //定义一个N个数的序列 
	for(i = 0;i<N;i++){
		scanf("%d",&array[i]);			
	}
	
	sort(array,array+N,cmp);
	int sum1 = 0;
	int sum2 = 0; 
	int sumDiff = 0;
	int numDiff = 0;
	int mid = N/2;
	
	for(i = 0;i < mid;i++){
		sum1 +=  array[i];
	}
	
	for(i = N -1;i >= mid ;i--){	
		sum2 +=  array[i];
	}
	if(N%2 == 0) {
		printf("0 %d",sum2-sum1);
	}else{
		printf("1 %d",sum2-sum1);
	}
	return 0;
}

5.执行结果