CF1833C题解

· · 题解

本文章同步发表于博客园

思路

首先，先明确一点：

接下来，我们要确定要都变成奇数还是偶数。

偶数？

如果是偶数，由于要同奇偶的两个数相减，结果才等于偶数。

又因为改变后的每个数都要 \gt0，所以，最小的奇数没有可以与其相减的奇数。所以，变成偶数是错误的。

但是

如果都是偶数的话，其实是可以的，所以要谈判。

现在目标明确了，把所有偶数变成奇数。

显然，我们可以贪心的将每个偶数匹配最小的奇数，如果发现有一个偶数比这个奇数小，则输出 NO，否则，输出 YES。

参考代码

#include<bits/stdc++.h>
using namespace std;
int t,n,a[200010];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int minn=0x7fffffff;
        int s1=0,s2=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(a[i]&1) minn=min(minn,a[i]);
            if(a[i]&1) s1++;
            else s2++;
        }
        if(s1==n||s2==n){
            printf("YES\n");
            continue;
        }
        bool f=0;
        for(int i=1;i<=n;i++){
            if(a[i]%2==0){
                if(a[i]<minn){
                    f=1;
                    break;
                }
            }
        }
        if(f) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}