「题解」洛谷 P7994 [USACO21DEC] Air Cownditioning B
在完成这一题之前，
你可以先完成 这道题。
这题本质上，其实是使用一个 区间修改操作，以 最少的修改次数 将序列 \(t\) 修改成序列 \(p\)。
我们可以定义一个 一维数组 \(differ\)，其初始化值为
\[differ_i=p_i-t_i\space(1\le i\le n) \]显然，
\(differ_i\) 的值有正有负，而我们的目标就是使每一个 \(differ_i=0\)。所以，要避免 负数的减少 和 正数的增加。
我们将数组 \(differ\) 分成若干段，使每一段中的 \(differ_i\) 非负 或 非正。
令 非负子串 减少以及令 非正子串 增加，
这就是我们要完成的 操作。
时间复杂度为 \(O(n)\)。
#include
#define int long long
using namespace std;
int n,p[100005],t[100005],differ[100005],ans;
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",p+i);
for(int i=1;i<=n;i++)
scanf("%lld",t+i),differ[i]=p[i]-t[i];
for(int i=0;i<=n;i++)
ans+=abs(differ[i]-differ[i+1]);
printf("%lld",ans>>1);
return 0;
}
提交记录