目录
思路篇
谷仓
拥挤的奶牛
弹簧高跷
滑雪场的高度差
代码篇
谷仓
拥挤的奶牛
弹簧高跷
滑雪场的高度差
思路篇
谷仓
题目描述
有一个圆形的谷仓，共有n个房间，按顺时针编号从1到n。现在有许多头奶牛，他们都有自己最喜欢的一个房间。傍晚回家时，奶牛们去找自己最喜欢的房间。如果发现被占了，他们就会按照顺时针方向找第一个空闲的房间住进去。现在请你输出最小的空闲的房间号。注意，这个答案和奶牛们回家的顺序是无关的。
2<=n<=3000000,1<=k<=10000,A,B的值在区间[0,10^9]。
输入
输入格式：
第一行两个整数n，k。
接下来有k行。每行4个整数，x,y,a,b.表示有x头奶牛喜欢f[1],f[2]……，f[y]。其中f[i]=(a*i+b)%n+1.
输出
输出格式：
输出最小的空闲房间号。
样例输入
10 3 3 2 2 4 2 1 0 1 1 1 1 7
样例输出
6
这道题，首先我们可以将F算出来，累计放在房间中，例如这个样例
第一次 f[1] = 7 f[2] = 9 0 0 0 0 0 0 3 0 3 0
第二次 f[1] = 2 0 2 0 0 0 0 3 0 3 0
第三次 f[1] = 9 0 2 0 0 0 0 3 0 4 0
好，我们的初始化就好了！
那怎么搞呢？
从后往前，找到最前面的空房间，压进去，这里不同于圆形谷仓，我们本来的位置是要留一头牛的，因为第一头牛肯定直接走喜欢的房间，不会向前找空房