AGC037C Numbers on a Circle（神奇思路）

Atcoder 全是神仙题……

先变成能不能从 \(b\) 到 \(a\)。操作变成一个数减掉旁边两个数。

考虑里面最大的且不和 \(a\) 中相等的那个数。它两边的数此时都不能操作，否则就减到非正数了。

而且应该要一直对这一位进行操作，直到等于 \(a_i\) 或者不是最大值为止。这样两边的数才能操作，或者真正确定无解。

用个堆模拟即可。

我的代码中复杂度……大概是两个 \(\log\) 吧。（辗转相除算一个）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200020,mod=998244353;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
struct item{
    int val,id;
    bool operator<(const item &i)const{return val<i.val;}
};
int n,a[maxn],b[maxn];
ll ans;
priority_queue<item> pq;
int main(){
    n=read();
    FOR(i,1,n) a[i]=read();
    FOR(i,1,n){
        b[i]=read();
        if(a[i]!=b[i]) pq.push((item){b[i],i});
    }
    while(!pq.empty()){
        int id=pq.top().id;pq.pop();
        int pre=id==1?n:id-1,nxt=id==n?1:id+1;
        if(b[id]-a[id]<b[pre]+b[nxt]) return puts("-1"),0;
        ans+=(b[id]-a[id])/(b[pre]+b[nxt]);
        b[id]-=(b[id]-a[id])/(b[pre]+b[nxt])*(b[pre]+b[nxt]);
        if(b[id]==a[id]) continue;
        pq.push((item){b[id],id});
    }
    printf("%lld\n",ans);
}

AGC037C Numbers on a Circle（神奇思路）

原文：https://www.cnblogs.com/1000Suns/p/11594718.html