题解归档 - cf2231B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2231B
• 本地来源：problems/cf2231B/idea.md
• 题目链接：https://codeforces.com/contest/2231/problem/B
• 原始标题：cf2231B Another Sorting Problem

思路

cf2231B Another Sorting Problem

思路

每个位置最终只有两种状态：不加，或加同一个正整数 k。

顺着相邻对维护可行的 k 区间与当前元素是否已加：

• 两边状态相同，则要求原本 a_i<=a_{i+1}。
• 左不加右加，会给出下界 k>=a_i-a_{i+1}。
• 左加右不加，会给出上界 k<=a_{i+1}-a_i。

代码维护两类状态的可行区间，扫完后任一非空即 YES。

验证

• python tools/run_exe.py cf2231B 通过官方样例。
• 小范围精确 brute：枚举所有加/不加位置并计算 k 上下界，99155 组与主解一致。

代码

来源：problems/cf2231B/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=4000000000000000000LL;
ll s[200005];
int main(){
    ll t,n,i,d,L0,R0,L1,R1,nL0,nR0,nL1,nR1,l,r;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(i=1;i<=n;i++) scanf("%lld",&s[i]);
        L0=1,R0=inf,L1=1,R1=inf;
        for(i=1;i<n;i++){
            d=s[i+1]-s[i];
            nL0=1,nR0=0,nL1=1,nR1=0;
            if(d>=0){
                if(L0<=R0){
                    nL0=L0,nR0=R0;
                }
                if(L1<=R1){
                    if(nL1>nR1) nL1=L1,nR1=R1;
                    else nL1=min(nL1,L1),nR1=max(nR1,R1);
                }
            }
            if(L0<=R0){
                l=max(L0,-d);
                r=R0;
                if(l<1) l=1;
                if(l<=r){
                    if(nL1>nR1) nL1=l,nR1=r;
                    else nL1=min(nL1,l),nR1=max(nR1,r);
                }
            }
            if(L1<=R1){
                l=L1;
                r=min(R1,d);
                if(l<1) l=1;
                if(l<=r){
                    if(nL0>nR0) nL0=l,nR0=r;
                    else nL0=min(nL0,l),nR0=max(nR0,r);
                }
            }
            L0=nL0,R0=nR0,L1=nL1,R1=nR1;
        }
        if(L0<=R0 or L1<=R1) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}