P17728 [SCP-J 2026] 染色 / color 题解

· · 题解

题目传送门：P17728 [SCP-J 2026] 染色 / color

目前给代码的题解好像没有这样简单完全不分讨的，害得我还以为自己橙题的思路都能假，原来只是太🍬了啊。

题目分析

首先答案就是两种颜色的最末元素减最初元素，而 a_1 是一定要减的，a_n 是一定要加的，除此之外再枚举对 a_i-a_j 即可。

条件是 i+1 \geqslant j，取等时即一个前缀一个后缀。否则即有穿插，很好理解。

所以维护一个后缀 \max，遍历到 i 时对 a_{i-1} 取 \max，然后全局对 \max - a_i 再取 \max。

关键是一个数可以即加又减，但不能加两次/减两次，即 i \neq n 且 j \neq 1。因此改 [1,n] 为 (1,n) 即可。

代码实现

#include<iostream>
using namespace std;
constexpr int N=200005;
int n,ans,mx,a[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>1;i--)mx=max(mx,a[i-1]),ans=max(ans,mx-a[i]);
    cout<<ans-a[1]+a[n];
    return 0;
}

AC 记录。

参赛感言

卡了卡了。