题解：SP7882 C1TABOVI - Tabovi

fish_love_cat · 2026-06-15 20:27:48 · 题解

翻做题记录里的灰题，发现怎么有开了荒但又没完全开的，补开荒。

双倍经验 P6446，完全一致。积木大赛被出烂了，这里还有一万倍经验说是。

不妨把目标和现状作差。

正负得换不同操作，考虑直接断开成若干截。

每一节你发现做的问题都是积木大赛。

懒得写了这一部分我选择直接抄袭上面那个菜鸡的专栏：

考虑贪心。

如果当前点比左边的点来的低，那么填左边的时候这里也可以顺便做掉。

否则我们就需要补足差距，考虑到依靠右边的操作来补齐其实不会比直接增加左边来的优，总次数是一样的，所以直接用后面的减去前面算出差值，得到需要再进行的操作次数即可。

于是就算完了，时间复杂度线性。

—— fish_love_cat

本题套用上面的做法即可做到线性。

#include<bits/stdc++.h>
using namespace std;
int ans,a[100005],b[100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i],a[i]=b[i]-a[i];
    for(int i=1;i<n;i++){
        if(a[i]*a[i+1]<0)ans+=abs(a[i]);
        else if(abs(a[i])>abs(a[i+1])) ans+=abs(a[i])-abs(a[i+1]);
    }
    ans+=abs(a[n]);
    cout<<ans;
    return 0;
}
// 巨大的虹色幻翼，从原本是菈琪旭‧尼克思‧瑟尼欧里斯的少女背后展开。