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

· · 题解

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

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

前言

典型的一道贪心题目，但是比赛的时候竟然没看出来，结果一道橙题切了一个小时，感觉自己好废物 QwQ。

题意简述

题目给出一个长度为 n 的数组 A，可以随意涂成两种颜色，如果当前格子 A_i 左侧存在同种颜色的格子 A_j，则当前格子的贡献是 A_i - A_j，如果不存在，那么贡献就是零，题目要求输出所有贡献和的最大值。

思路讲解

首先通过数据范围可以知道如果你不想只拿一半分，暴力肯定是没戏的，所以让我们来想一想怎么优化，在本子上写一写我们很容易发现一个情况，对于一个以 A_i 开始以 A_j 结束的完整色块，它提供的贡献就是 A_j - A_i，这很容易证明，因为后一项把前一项减去的给加上了，最后只剩下这个，这个结论很有意思，它可以把原本 O(n) 时间完成的任务缩短到 O(1) 的时间完成，但是很明显只靠它并不能完成求解，因为还存在另一种颜色，所以我们来思考一下，这个结论是否还有什么其他性质。

因为增加了一种颜色，所以我们来分类讨论一下：

  1. 红蓝互不干涉，分成两大块：很明显可以直接用我们得到的公式计算，假设红色从 A_1 开始到 A_b 结束，蓝色从 A_r 开始到 A_n 结束，那么可以发现这时总贡献的值就是 (A_n - A_r) + (A_b - A_1)。
  2. 红色非常大包裹住了蓝色：让我们写出它的贡献，假设红色从 A_1 开始到 A_n 结束，蓝色从 A_b 开始到 A_r 结束，那么总贡献就是 (A_n - A_1) + (A_r - A_b)，是不是觉得有些眼熟？让我们先总结第三类。
  3. 红色开头蓝色结尾，中间相互穿插：前两种情况都是两段纯色部分，互相穿插的情况我们归纳的情况还能用吗？答案是可以，因为我们想一下证明的过程，发现即使中间互不连接，最终贡献依然是 A_j - A_i，所以我们假设红色从 A_1 开始到 A_r 结束，蓝色从 A_b 开始到 A_n 结束，那么答案就是 (A_n - A_b) + (A_r - A_1)。

相信大家这时候已经发现了，这几个结论的公式长得好像啊，在保证 1 \le b < r \le n 的情况下，除了第一种情况，它们都可以转换成 (A_n - A_1) + (A_r - A_b)，或许大家会问，那情况一怎么办，观察一下会发现，情况一要求 r - 1 = b，这代表着我们只需要 O(n) 的时间枚举一遍所有相邻差中的最大值，情况一的答案就有了，后两种情况也很简单，因为 A_n - A_1 是定值，我们只需要找到最大的 A_r - A_b 就行了，很容易想到维护一个前缀最小值就行了。

复杂度分析

因为三种情况都是从头到尾遍历数组就能解决，所以时间复杂度只有 O(n)，空间上存个输入就行，所以也是 O(n)。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=200010;
int n;
long long arr[MAX_N];


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    long long base=arr[n]-arr[1];  //基础定值

    //情况一
    long long best=0;  //数据可能超int记得开long long保险
    for(int i=1;i<n;i++){
        best=max(best, arr[i]-arr[i+1]);
    }

    //情况二和情况三
    if(n>=3){
        long long pre=arr[2];  //维护前缀最小值
        for(int j=3;j<=n-1;j++){
            best=max(best, arr[j]-pre);
            pre=min(pre, arr[j]);
        }
    }   
    cout<<best+base<<'\n';
    return 0;
}

AC 记录