C - sum（牛客小白月赛102）

题目链接：C - sum

题目描述：

示例说明：

解：

这题典型的贪心问题，是求最小的操作次数。首先我们可以先算出这n个数的和s，s和sum的大小有三种情况。当s = sum时，一个数字也不用修改，答案为0。而剩下的两种情况可以合为一种情况来做。首先我们要知道如果把这n个数都变为相反数， 则s也会变为s的相反数，当把sum也变为sum的相反数时，所需的次数是一样的。(因为题目中修改后的某个数的值x是在[-10000,10000]之间，是对称的。）知道这接下来就好办了。

方法一：

以s > sum来做，要使s尽可能接近sum的值并且次数最少。可以先从这n个数最大的数开始，用s减去这个数然后再减去10000，比较 s和sum的关系，如果 s还是>sum 继续用当前的s减去第二大的这个数再减去10000。直到s <= sum时，则从头到尾经过的次数为最小次数。

code：

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 2e5 + 10;
int a[N];
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	while( t -- ) {
		int n, sum, s = 0; 
		cin >> n >> sum;
		for(int i = 1; i <= n; i ++ ) {
			cin >> a[i];
			s += a[i];
		}
		if(s == sum) { //s = sum时 则不需要修改次数 
			cout << "0" << endl;
			continue; 
		}
		if( s < sum) { // s < sum时 全部取反则可变为 s > sum  
			for(int i = 1; i <= n; i ++) a[i] = -a[i];
			s = -s; sum = -sum;
		}
		sort(a + 1, a + 1 + n);
		
		//能进入此循环的 表明此时 s > sum 
		for(int i = n; i >= 1; i -- ) { //s > sum 要使s更加的接近sum 首先从最大的那个修改 
			s = s - a[i] - 10000;
			if(s <= sum ) {
				cout << n - i + 1 << endl; 
				break;
			} 
		}
		
	}
	return 0;
}

方法二：

以 s < sum来做，和上面的思想是一样的，话不多说 直接上code。

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 2e5 + 10;
int a[N];
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	while( t -- ) {
		int n, sum, s = 0;
		cin >> n >> sum;
		for(int i = 1; i <= n; i ++ ) {
			cin >> a[i];
			s += a[i];
		}
		if(s == sum) { //s = sum时 则不需要修改次数 
			cout << "0" << endl;
			continue; 
		}
		if( s > sum) { // s > sum时 全部取反则可变为 s < sum  
			for(int i = 1; i <= n; i ++) a[i] = -a[i];
			s = -s; sum = -sum;
		}
		sort(a + 1, a + 1 + n);
		
		//能进入此循环的 表明此时 s < sum 
		for(int i = 1; i <= n; i ++ ) { //s < sum 要使s更加的接近sum 首先从最小的那个修改 
			s = s - a[i] + 10000;
			if(s >= sum ) { 
				cout << i << endl; 
				break;
			} 
		}
		
	}
	return 0;
}

GAME OVER！

END！