洛谷题面

题目大意

给定一个数列，这个数列有 \(n\) 个数，你可以对数列进行任意次操作。操作定义为：

• 在数列中选择两个数 \(a_{i}\)，\(a_{j}(i\neq j,1\le a_i,a_j\le10^9)\)，将它们的值分别减 \(1\)。

求若干次操作后该数列的 \(n\) 个数是否可能都为 \(0\)。可能则输出 \(\textsf{YES}\)，否则输出 \(\textsf{NO}\)。

题目分析

结论及相关证明

\(\boxed{1}:\) 输出答案为 \(\textsf{NO}\)，当有奇数个奇数时。

证明结论 \(\boxed{1}:\)

不妨设序列中有 \(2k+1(1\le k\le\left\lfloor\dfrac{n-1}{2}\right\rfloor\texttt{~且~}k\texttt{~为正整数})\) 个奇数，并且这些奇数挤在一堆（不影响结果），分别为 \(A_1,A_2,\cdots,A_{2k},A_{2k+1}\)。

由于这些奇数的和（即 \(\sum\limits_{i=1}^{2k+1}A_i\)）一定为奇数，那么我们将这一堆奇数不停地减去 \(2\)，最后一定会剩余一个奇数；

而不论有多少偶数，最后都不可能得到一个奇数，所以就不可能与其抵消。

得证。

举个例子：

一个序列为 3,5,7,9,11,2,10，如果不停地执行操作，最后一定会变成这个样子 0,0,0,0,0,0,1。

\(\boxed{2}:\) 输出答案为 \(\textsf{NO}\)，当 \(\max~a_i >\sum\limits_{i=1}^{n}a_i-\max~a_i\)，即数列中的最大值严格大于其它所有数的总和时。

证明结论 \(\boxed{2}:\)

先将序列中所有数升序排列。

\(\because a_n>a_1+a_2+\cdots+a_{n-1}\)

两边同时减去 \(a_1+a_2+\cdots+a_{n-1}\) 不等式仍成立：

\(\therefore a_n-a_1-a_2-\cdots-a_{n-1}>0\)

很明显不可能，于是得证。

---

时间复杂度 \(\Theta(N)\)

代码

//2021/10/4

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <algorithm> 

#define int long long 

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

namespace Newstd
{
	inline int read()
	{
		char c;
		bool flag=false;
		while((c=getchar())<'0' || c>'9')
		{
		    if(c=='-') flag=true;
		}
		int res=c-'0';
		while((c=getchar())>='0' && c<='9')
		{
		    res=(res<<3)+(res<<1)+c-'0';
		}
		return flag?-res:res;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar('-');x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=100005;

const int INF=0x3f3f3f3f3f3f3f3f;

int a[ma];

#undef int

int main(void)
{
	#define int long long
	
	int n=read();
	
	int sum(0),maxx=-INF;
	
	int num(0);
	
	for(register int i=1;i<=n;i++)
	{
		a[i]=read();
		
		if(a[i]%2==1)
		{
			num++;
		}
		
		sum+=a[i];
		
		maxx=max(maxx,a[i]);
	}
	
	sum-=maxx;
	
	if(maxx>sum)
	{
		cek("NO");
	}
	
	else if(num%2==1)
	{
		cek("NO");
	}
	
	else
	{
		puts("YES");
	}
	
	return 0;
}