自动搬运

查看原文

来自洛谷，原作者为

	小手冰凉 **

搬运于2025-08-24 21:45:13，当前版本为作者最后更新于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;
}