原题描述：链接：https://ac.nowcoder.com/acm/contest/51208/B
原题题解：链接：https://ac.nowcoder.com/discuss/1121134
题意：给出长度为n的正整数序列a, b，可以选择相邻的两个数传递2，问最少传递多少次使得两个正整数序列对应位置相等，如果无法使其相等输出-1
分析：当\(a[i]\equiv b[i](mod\) \(2)\)并且\(\sum_{i=1}^n a_{i}= \sum_{i=1}^nb_i\)时，才能有解
感性地说：对于i这个位置来说，如果序列a左边的数字之和（包含i这个数字）的比b的大，那么说明a序列需要从i到i+1传递两者相差的数值，比b小就是说明b序列从i到i+1传递两者相差的数值或者是考虑成i+1到i需要传递两者相差的数值
正式地说：见牛客原题题解
总结：对于这种需要一个一个位置传递算贡献的题，考虑当前位置与相邻的位置的传递对答案的贡献，然后加在一起即可
正解AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//-----------------------
void solve()
{
int n;
cin>>n;
vector<ll> a(n+1), b(n+1);
for(int i=1; i<=n; i++)cin>>a[i];
for(int i=1; i<=n; i++)cin>>b[i];
ll ans=0;
for(int i=1; i<=n; i++){
if(a[i]%2!=b[i]%2){
cout<<-1<<'\n';
return;
}
a[i]+=a[i-1];
b[i]+=b[i-1];
ans+=(max(a[i], b[i])-min(a[i], b[i]))/2;
}
if(a[n]!=b[n]){
cout<<-1<<'\n';
}else{
cout<<ans<<'\n';
}
}
int main(void)
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T=1;cin>>T;
while(T--)solve();
return 0;
}
思路不清的双指针AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
//----------------------
void solve()
{
int n;
cin>>n;
vector<int> a(n), b(n);
ll d1=0, d2=0;
vector<P> buc1, buc2;
for(auto &v:a)cin>>v;
for(auto &v:b)cin>>v;
ll ans=0;
int loc1=0, loc2=0;
while(1){
while(loc1<n && a[loc1]<=b[loc1])loc1++;
while(loc2<n && a[loc2]>=b[loc2])loc2++;
if(loc1==n && loc2==n)break;
if(loc1==n && loc2!=n){
cout<<-1<<'\n';
return;
}
if(loc1!=n && loc2==n){
cout<<-1<<'\n';
return;
}
int d1=a[loc1]-b[loc1], d2=b[loc2]-a[loc2];
if(d1%2 || d2%2){
cout<<-1<<'\n';
return;
}
if(d1>=d2){
b[loc1]+=d2;
b[loc2]-=d2;
ans+=1LL*d2/2*abs(loc1-loc2);
}else{
a[loc2]+=d1;
a[loc1]-=d1;
ans+=1LL*d1/2*abs(loc1-loc2);
}
}
for(int i=0; i<n; i++){
if(a[i]!=b[i]){
cout<<-1<<'\n';
return;
}
}
cout<<ans<<'\n';
}
int main(void)
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T=1;cin>>T;
while(T--)solve();
return 0;
}