能给下原网站吗方便测 @[ive_wonyoung](/user/1043012)
by weak_in_code @ 2024-04-12 20:45:45
@[weak_in_code](/user/753640) 大佬可能不太行 因为这是我们校oj啊啊 要登陆什么 ~~如果大佬愿意登我账号的话当我没说~~
by ive_wonyoung @ 2024-04-12 20:50:43
@[ive_wonyoung](/user/1043012) 能多给几组数据吗,$a_i\geq b_i$ 的情况应该没问题了,其他的暂时不知道
by weak_in_code @ 2024-04-12 21:07:27
```cpp
#include<bits/stdc++.h>
#define sd std::
#define int long long
#define inf 0x3f3f3f3f
#define linf 1e18
#define il inline
#define db double
#define ldb long double
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define f(i,a,b) for(int i=(a);i>=(b);i--)
#define MIN(x,y) (x<y?x:y)
#define MAX(x,y) (x>y?x:y)
#define me(x,y) memset(x,y,sizeof x)
#define pii sd pair<int,int>
#define umap(x,y) sd unordered_map<x,y>
#define pque(x) sd priority_queue<x>
#define X first
#define Y second
#define kg putchar(' ')
#define Fr(a) for(auto it:a)
#define dbg(x) sd cout<<#x<<": "<<x<<sd endl
il int read(){int w=1,c=0;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) c=(c<<3)+(c<<1)+ch-48;return w*c;}
void printt(int x){if(x>9) printt(x/10);putchar(x%10+48);}
il void print(int x){if(x<0) putchar('-'),printt(-x);else printt(x);}
il void put(int x){print(x);putchar('\n');}
il void printk(int x){print(x);kg;}
const int N=1e5+10;
int n;
int a[N],b[N],c[N],d[N];
sd vector<pii> s;
signed main()
{
n=read();
F(i,1,n) a[i]=read();
F(i,1,n) b[i]=read();
F(i,1,n) c[i]=a[i]-b[i];
int cnt=1;
F(i,2,n)
{
if(c[i]!=c[i-1]) s.emplace_back(cnt,c[i-1]),cnt=1;
else cnt++;
}
s.emplace_back(cnt,c[n]);
int p=0;
for(auto it:s)
{
d[++p]=it.Y;
// printk(it.X),put(it.Y);
}
int sum=0;
F(i,1,n)
{
// put(d[i]);
if(d[i]*d[i-1]<0) sum+=abs(d[i]);
else if(d[i]>d[i-1]&&d[i]>0) sum+=d[i]-d[i-1];
else if(d[i]<d[i-1]&&d[i]<0) sum+=abs(d[i]-d[i-1]);
}
return put(sum),0;
}
/*
5
1 5 3 3 4
1 2 2 2 1
*/
```
by weak_in_code @ 2024-04-12 21:21:24
看看这个能不能。
by weak_in_code @ 2024-04-12 21:21:51
@[ive_wonyoung](/user/1043012)
```cpp
//考虑到选择ai加1还是bi减1不影响ai等于bi,因此考虑ai和bi的差di
//由于区间,想到差分(显然只能对d差分)
#include <iostream>
#define maxn 100005
using namespace std;
int n, x, y, a[maxn], b[maxn], d[maxn];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i], d[i] = a[i] - b[i];
for (int i = n; i; i--)
if ((d[i] -= d[i - 1]) > 0)
x += d[i];
else
y -= d[i];
cout << max(x, y);
return 0;
}
```
by lcy666666 @ 2024-04-12 21:25:33
@[weak_in_code](/user/753640) 大佬a了!!!谢谢大佬 但是我有点没看懂您代码的思路啊啊啊
by ive_wonyoung @ 2024-04-12 21:34:32
@[lcy666666](/user/491219) 大佬最后一个for不太理解 差分我也没了解过 或许有关于差分的文章之类的吗 但还是谢谢大佬
by ive_wonyoung @ 2024-04-12 21:37:31
额,我怕我讲的不大对呢。。。
这一篇讲的还可以:[link](https://blog.csdn.net/weixin_73888239/article/details/128384249)(主要是一维差分,二维差分比较罕见),一般看到区间加减就可以考虑一下差分
(另外能否帮我测试一下我的代码是否正确,谢谢
@[ive_wonyoung](/user/1043012)
by lcy666666 @ 2024-04-12 21:57:53
@[lcy666666](/user/491219) 正确的 大佬真的很厉害 谢谢大佬
by ive_wonyoung @ 2024-04-12 22:13:57