家庭菜園4 题解

water_three · 2021-12-12 16:17:30 · 题解

前置知识：

差分数组及 P2367 语文成绩。

性质：

• 由上题和差分数组的基本概念我们可以得知：选定一个区间 L 和 R-1 让这个区间里的数加 1，在差分数组里的实质是将 f_L 加 1 , f_R 减 1.

• 因为题目要求保持严格单调递增、减，所以最后差分数组中除 f_1 外不能有 0.

因为题目要求一个 k 使得 a_1 到 a_k 为严格升序排列，反应在差分数组中表现为 f_2 到 f_k 均为正数---所以在 a_2 到 a_k 中，后一个数总比前一个数大。

同理让 k 使 a_k 到 a_n 为严格降序排列，需要使 f_k 到 f_n 均为负数（不包含 f_k）。

实现：

由此我们可以每次通过操作选定一个区间 L 和 R 让这个区间里的数加1 ，最终要使得 f_k 前面均为正数，f_k 后面均为负数。

我们设 A 为 k （包括 k ）以前的非正数减 1 的绝对值之和（因为严格单调递增，所以不能为 0），B 为 k 以后的非负数加 1 之和，因此很容易想出最少的操作次数就等于 A 和 B 中的最大值。

k 的转移：

那么，我们可以枚举当 k 等于 1，2 到 n. 然后取操作次数最小值。

• 当 k 从 1 转移到 2 时，如果 f_2 为正数，那么 k 右边的非负数和会减 f_2 再减 1.

• 如果为 0，因为严格单调递增、减，所以 k 右边的非负数和会减 1, 左边的非正数之和会加 1.

• 如果为负数，那么 k 左边的非正数之和会加 f_2 的绝对值，再加 1.

优化

• 对于输入本身就是严格递增或递减序列，我们可以直接输出 0.

• 当只有两个数时，如果两数相等，输出 1，否则输出 0.

代码：

#include<bits/stdc++.h>
using namespace std;
long long A,B,pan1,pan2;//A为k左边负数个数，B为K右边正数个数。 
long long ans=1e20;//ans一定要初始化特别大 
const int n=2e5+10;
long long N,a[n],f[n];//f[]为方差 
int main() {
    cin>>N;
    for(long long i=1; i<=N; i++) {
        cin>>a[i];
        if(i!=1)f[i]=a[i]-a[i-1];
        if(f[i]>=0&&i!=1)B+=abs(f[i])+1;//预处理当k==1时f[1]右边有多少非负数
        if(i!=1&&a[i]>=a[i-1])pan2=0;//不是递减序列 
        if(i!=1&&a[i]<=a[i-1])pan1=0;//不是递增序列 
    }
    if(pan2||pan1) {//特判1 
        cout<<"0"<<endl;
        return 0;
    }
    if(N==2) {//特判2 
        if(a[1]==a[2]) {
            cout<<"1"<<endl;
            return 0;
        } else {
            cout<<"0"<<endl;
            return 0;
        }
    }
    ans=min(ans,max(A,B));//处理当k=1时操作步数max（A，B）；
    for(long long i=2; i<=N; i++) {//k的转移 
        if(f[i]>0) {
            B--;
            B-=abs(f[i]);
        } else if(f[i]==0) {
            B--;
            A++;
        } else {
            A+=abs(f[i]);
            A++;
        }
        ans=min(ans,max(A,B));
    }
    cout<<ans<<endl;
   return 0;
}