P6446TABOVI 贪心题解

Math_rad_round · 2020-04-21 07:25:47 · 题解

P6446

题意简述：

给你两个长 n 的数组 p_i，k_i

每一次操作可以将任意长度的区间每一个数 \pm 1

求把 p_i 转换成 k_i 的最小操作次数

我们可以想到，我们关心的是 p_i 和 k_i 的差值

所以可以设 a_i=p_i-k_i

我们可以从左往右慢慢递推

假设在 a_i 之前我们加上了 l 排（删去就是负数）

可以发现，l=a_{i-1}，因为我们已经处理好了a_{i-1}

如果a_i和a_{i-1}的操作种类一样，那么我们直接把原来a_{i-1}用的操作右界限移一位覆盖a_i，也就是节省了|a_{i-1}|次操作，剩余的操作次数就是max(0,|a_i|-|a_{i-1}|)

否则，a_{i-1}的操作不能沿用，需要单独为a_i操作。次数为abs(a_i)

依次不断递推，每次将ans加上额外用的操作数。最终ans就是答案

复杂度空间O(n)，时间O(n)，达到了理论下限。

AC代码:

#include<iostream>
using namespace std;
int a[100000];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int a1;
        cin>>a1;
        a[i]=a1-a[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]>0&&a[i-1]>0)ans+=max(0,a[i]-a[i-1]);
        else if(a[i]>0&&a[i-1]<=0)ans+=a[i];
        else if(a[i]<0&&a[i-1]<0)ans+=max(0,a[i-1]-a[i]);//因为都是负数 
        else ans+=-a[i]; 
    }
    cout<<ans;
}

~~这题数据是真的水~~

P6446TABOVI 贪心 题解

P6446TABOVI 贪心题解