Codeforces Round #726 (Div. 2) A. Arithmetic Array

LINK

计算 s u m = ∑ i = 1 n a i sum=\sum\limits_{i=1}^na_i sum=i=1∑n​ai​

设添加了 x x x个数,和为 f f f

有 s u m + f = n + x sum+f=n+x sum+f=n+x

x = s u m − n + f x=sum-n+f x=sum−n+f

f ∈ [ 0 , inf ⁡ ] f\in[0,\inf] f∈[0,inf],显然取 0 0 0最优,于是 x = s u m − n x=sum-n x=sum−n

然而 x x x不能是负数,所以如果 s u m − n sum-n sum−n为负数的话答案是 1 1 1

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int maxn = 3e5+10;
int n,t,a[maxn];
int main()
{
	int t; cin >> t;
	while( t-- )
	{
		scanf("%d",&n );
		int sum = 0;
		for(int i=1;i<=n;i++)	scanf("%d",&a[i] ), sum += a[i];
		if( sum-n<0 )	cout << 1 << endl;
		else	cout << sum-n << endl;
	}
	return 0;
}
上一篇:蓝桥杯——动态规划专题


下一篇:SpringBoot胖jar转瘦jar