CF1473A Replacing Elements 题解

CF1473A Replacing Elements题目

题面描述

给定一个长度为 n 的序列 a ，每次在 a 中选三个数，可以将其中一个变成另外两个数的和。

求若干次操作后是否使所有数都小于等于 d 。

分析

显然我们想让最后序列中每个数尽可能的小。

这里有两种情况（样例比较良心两种情况都包含了！）

①一开始序列中的每一个就是小于等于 d 的。那么显然直接输出 YES 就行了。

②然后我们来考虑一开始序列中有数大于 d 的，于是我们希望用小的数将他们替换。不难想因为数是越加越大的，所以最小的用来替换数就是一开始序列中最小和次小的数之和。所以我们只要考虑一开始序列中最小数和次小数之和是否小于等于 d 即可。（如果成立，那么所有原大于 d 的数都可以被此数替换至合法。）

所以题目就变为维护区间最小值和次小值，这里我直接暴力判断了

AC记录

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
ll read() 
{
    ll res=0,f=1;
    char c=getchar();
    while(!isdigit(c) && c!='-') c=getchar();
    if(c=='-') f=-1,c=getchar();
    while(isdigit(c)) res=(res<<1)+(res<<3)+c-48,c=getchar();
    return res*f;
}
int a[maxn];
int main()
{
    int T=read();
    while(T--)
    {
        int n=read(),d=read();
        int min1=1e9,min2=1e9;
        bool bl=1;               //bl 表示是否一开始序列中的数就都小于d 
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            if(a[i]>d) bl=0;
            if(a[i]<min1)        // 暴力维护最小值和次小值 
            {
                min2=min1;
                min1=a[i];
            }
            else
                if(a[i]<min2) min2=a[i];
        }
        if(bl || min1+min2<=d) puts("YES");
        else puts("NO");
    }
    return 0;
}