AcWing 1603. 贪心
原题链接
简单
作者:
𝓒𝓸𝓬𝓪𝓒𝓸𝓵𝓪_8
,
2021-01-25 21:31:55
,
所有人可见
,
阅读 356
贪心
首先要使|n1 - n2|最小,那么就是平分或者其中一个数组多一个
为了使|S1 - S2|更大,所以如果无法平分那么就把最后这一个给和最大的数组,从而来使差值更大
那么就很容易想到一个数组全部放小的数,一个数组全部放大的数
因此直接排序然后小的一半作为第一个数组,大的那一半数字则作为第二个数组
时间复杂度(nlogn + n)
C++ 代码
#include <bits/stdc++.h>
using namespace std ;
int a[100010] ;
int main(){
int n ;
cin >> n ;
for(int i = 0 ; i < n ; ++ i)
cin >> a[i] ;
sort(a , a + n) ; //先排序
int l = 0 , r = n - 1 ; //双指针,l用来计算小的数组,r用来计算大的数组
int s1 = 0 , s2 = 0 , w = 0 ; //分别计算两个数组的元素和,w用来记录|n1 - n2|
while(l < r){
s1 += a[l ++] ; //分别计算两个数组的和
s2 += a[r --] ;
}
if(l == r){
s2 += a[r] ; //如果数的个数是奇数个,那就给和大的数组多给一个数拉大差值
w = 1 ; //两个数组的长度差值为1
}
cout << w << " " << s2 - s1 ;
return 0 ;
}