贪心
思路参考了https://www.acwing.com/solution/content/114260/
但是下面的代码可能更直白一些
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
int n;
int p[N],t[N],a[N];
int main()
{
cin>>n;
for (int i = 1; i <= n; i ++ ) cin>>p[i];
for (int i = 1; i <= n; i ++ ) cin>>t[i];
for(int i=1;i<=n;i++) a[i]=p[i]-t[i];//现在和希望的差值数组
int res=0;
int pre=0;
for (int i = 1; i <= n; i ++ )//只计算a>0的连续一段区间
{
int now=a[i];
if(a[i]<=0)
{
pre=0;
continue;
}
res+=max(0,a[i]-pre);
pre=a[i];
}
pre=0;
for (int i = 1; i <= n; i ++ )//只计算a<0的连续一段区间
{ //我们可以类似于按照a>0的进行操作 一会取个负号就ok
int now=a[i];
if(a[i]>=0)
{
pre=0;
continue;
}
a[i]=-a[i];//负号
res+=max(0,a[i]-pre);
pre=a[i];
}
cout<<res;
return 0;
}