正题
题目链接:https://www.luogu.com.cn/problem/AT5160
题目大意
给出两个长度为\(n\)的环序列\(a\)和\(b\)，每次你可以让\(a\)中的一个数变为它和相邻两个的和。
求最少的步数将\(a\)变为\(b\)。
\(1\leq n\leq 10^5,1\leq a_i,b_i\leq 10^9\)
解题思路
被蓝题D烂了。
考虑反过来做，每次操作为\(B_i=B_i-B_{i-1}-B_{i+1}\)。
然后考虑怎么搞这个东西，注意到\(B_i\)不能够减到负数所以同理也不能减到小于\(A_i\)，考虑如果对于一个\(B_i\geq B_{i-1}+B_{i+1}\)那么此时位置\(i-1\)和\(i+1\)显然都是不能动的，那么我们动\(B_{i}\)就一定是最优的。
还有如果\(B_i=A_i\)时那么\(B_i\)就是不可以再操作的了。
具体地我们每次找到最大的可操作的\(B_i\)，然后把它减到不能再减即可，然后过程中判断是否无解即可。
由于每次至少减半所以每个数应该会操作最多\(log\)次。
时间复杂度：\(O(n\log n\log w)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N=2e5+10;
ll n,a[N],b[N],ans;
priority_queue<pair<int,int> > q;
ll pl(ll x){return (x==1)?n:(x-1);}
ll pr(ll x){return (x==n)?1:(x+1);}
signed main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=1;i<=n;i++){
scanf("%lld",&b[i]),q.push(mp(b[i],i));
if(a[i]>b[i])return puts("-1")&0;
}
while(!q.empty()){
ll x=q.top().second;q.pop();
if(b[x]==a[x])continue;
ll d=b[pl(x)]+b[pr(x)];
if(b[x]-d<a[x])break;
ans+=(b[x]-a[x])/d;
b[x]-=(b[x]-a[x])/d*d;
if(b[x]!=a[x])q.push(mp(b[x],x));
}
if(q.size())puts("-1");
else printf("%lld\n",ans);
return 0;
}