signed

QiShunwang

“诚信为本、客户至上”

PAT 1113 Integer Set Partition

2021/4/26 21:33:42   来源:

在这里插入图片描述
题目大意:
给一个数的序列,把它分成两个集合,首先满足两个集合各自的数的个数之差最小,再满足两个集合各自的数的总和之差最大。

思路:
把输入的数据的放入vector里进行排序,如果是数的个数是偶数,个数之差为0,个数是奇数,个数之差为1,把最中间的数分别放至两边比较哪个差的比较大,就输出哪个。

代码:

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int> v(n);
	for(int i=0;i<n;i++) cin>>v[i];
	sort(v.begin(),v.end());
	int s1=0,s2=0;
	for(int i=0;i<v.size()/2;i++) s1+=v[i];
	if(v.size()%2==0){
		for(int i=v.size()-1;i>=v.size()/2;i--) s2+=v[i];
		printf("0 %d",abs(s2-s1));
	}
	else{
		for(int i=v.size()-1;i>v.size()/2;i--) s2+=v[i];
		printf("1 ");
		printf("%d",abs(s2+v[v.size()/2]-s1)>abs(s1+v[v.size()/2]-s2)?abs(s2+v[v.size()/2]-s1):abs(s1+v[v.size()/2]-s2));
	}
	
	return 0;
}

在这里插入图片描述