题解 P3090 【[USACO13NOV]空荡荡的摊位Empty Stalls】

小手冰凉 · 2018-02-21 09:51:05 · 题解

这题题目中给了一个比较重要的信息

"很明显，问题的答案与奶牛进入谷仓的顺序无关。"

这句话告诉了我们这题的一个思路：将所有数据一起处理

我们可以先假设所有牛棚可以放无数个奶牛

然后一个一个往后推

这样得出的答案就是直接做的答案（当然牛棚和牛具体对应的序号是不知道的）

要注意可能爆int，以及第一遍扫过以后可能有的到了头一个牛棚，要再来一遍

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3000000;
int n;
int ans[N];
int x,y,a,b,k;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}
signed main()
{
    n=read();k=read();
    while(k--){
        x=read();y=read();a=read();b=read();
        for(int i=1;i<=y;i++){
            ans[(a*i+b)%n]+=x;
        }
    }
    for(int i=0;i<n;i++){
        if(ans[i]>0)ans[(i+1)%n]+=ans[i]-1,ans[i]=1;
    }
    while(ans[0]>1)
        for(int i=0;i<n;i++){
            if(ans[i]>0)ans[(i+1)%n]+=ans[i]-1,ans[i]=1;
        }
    for(int i=0;i<n;i++)
        if(ans[i]==0){
            cout<<i<<endl;
            return 0;
        }
    return 0;
}