[USACO13NOV]空荡荡的摊位Empty Stalls

本文主要是介绍[USACO13NOV]空荡荡的摊位Empty Stalls，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Luogu P3090 [USACO13NOV]空荡荡的摊位Empty Stalls

分析

遇到一道思维题，难度不大，记录一下。

题意：

有很多类牛，每类牛有很多批，同种类的每一批又有相同个数的牛，他们喜欢相同一个位置；每一类的第i批都喜欢 Ai+B 号位置；每一个位置最终只能安放一头牛；牛中意的位置被占领后，它将向后寻找最近的没有被占领的位置进行占领。所有位置是成环的，即 $1 \to 2 \to …… \to n \to 1 \to ……$ 。给出各参数，求出所有牛都有归属后，所有没有牛的位置中，编号最小的位置。

思想：

模拟分配位置过程即可：
先扫描一次，将能分配的位置都分配上；
同时将每个位置上多余的牛带到下一个；
将牛推到第一个位置上进行第二轮扫描；
那么最多两次循环就可以全部分配完毕；
再扫描一次，寻找最小未被占领的位置；
一共最多三次循环。 $O(3 n)$ 绰绰有余。

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=3000002;
int f[maxn];
int n,k;
//分配过程
void circle()
{for(int i=0;i<n-1;i++)if(f[i]>1)      f[i+1]+=f[i]-1,f[i]=1;
}int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=k;i++){int x,y,a,b,num;scanf("%d%d%d%d",&x,&y,&a,&b);num=b;for(int j=1;j<=y;j++){num=(num%n+a%n)%n;f[num]+=x;}}circle();if(f[n-1]>1){f[0]+=f[n-1]-1,f[n-1]=1;circle();}for(int i=0;i<n;i++)    if(!f[i])   {printf("%d",i);return 0;}return 0;
}