题解：CF2026B Black Cells

__Aha__ · 2024-11-26 16:16:50 · 题解

题目传送门

先给出AC记录。

题目大意

输入一个有 n 个数的单调递增的序列 a，请求出相邻两数之间差的最大值，已经求完差的数不能再使用。

在任意位置 i 你可以使用一个魔法（仅能使用 1 次），这个魔法能创造一个数 a_{i}+1 使 a_{i} 和 a_{i}+1 做差（这样的作用是使有一个差为 1）。

思路

一道简单贪心题。

显然，为了使两数之间差最小，肯定能使用魔法就使用，但一定注意只有 n 为奇数时才能使用（其实这时一定会使用，不管是题目要求还是答案最优的情况）。因为如果 n 为偶数时，则序列中的数刚好两两配对。

又因为数据范围过小，支持 O(TN^2) 的时间复杂度，所以直接枚举在哪个位置使用魔法。

直接看代码。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,n,a[2005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        ll ans;
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n%2){//n 为奇数。
            ans=1e18;//答案初始定义最大值。
            for(int i=1;i<=n;i++){//枚举在 i 处使用魔法。
                ll s=1;//使用魔法后差最小为 1。
                for(int j=1;j<i;j+=2) s=max(s,a[j+1]-a[j]);
                for(int j=i+1;j<=n;j+=2) s=max(s,a[j+1]-a[j]);
                //跳过 i 计算差值
                ans=min(ans,s);//求最大差中的最小值。
            }
        }
        else{
            ans=1;
            for(int i=1;i<=n;i+=2) ans=max(ans,a[i+1]-a[i]);
            //n 为偶数则直接计算最大差
        }
        cout<<ans<<"\n";
    }
    return 0;
}