首页 > 其他 > 详细

agc 037 C

时间:2019-08-21 22:20:40      阅读:125      评论:0      收藏:0      [点我收藏+]

其实我们很容易注意到一个性质,如果我们要减bi的话,他一定比两边的数大。
所以为什么我注意到了还是没过
然后用个队列搞一下就行了,每对一个数操作完的时候,我们就check它两侧的两个数看能否扔进去。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int a[N],b[N],n;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    queue<int> q;
    for(int i=0;i<n;i++){
        if(b[i]-a[i]>=b[(i-1+n)%n]+b[(i+1)%n])
            q.push(i);
    }
    ll ans = 0;
    while (!q.empty()){
        int i = q.front();q.pop();
        int k = (b[i]-a[i])/(b[(i+n-1)%n]+b[(i+1)%n]);
        b[i]-=k*(b[(i-1+n)%n]+b[(i+1)%n]);ans+=k;
        i=(i+n-1)%n;
        if(b[i]-a[i]>=b[(i+n-1)%n]+b[(i+1)%n])
            q.push(i);
        i=(i+2)%n;
        if(b[i]-a[i]>=b[(i+n-1)%n]+b[(i+1)%n])
            q.push(i);
    }
    bool f=1;
    for(int i=0;i<n;i++){
        if(a[i]!=b[i]){
            f=0;
            break;
        }
    }
    if(f)cout<<ans<<endl;
    else cout<<-1<<endl;
}

agc 037 C

原文:https://www.cnblogs.com/MXang/p/11391309.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!