考试（四）（标题未取好）

目录

思路篇

谷仓

拥挤的奶牛

弹簧高跷

滑雪场的高度差

代码篇

谷仓

拥挤的奶牛

弹簧高跷

滑雪场的高度差

思路篇

谷仓

题目描述

有一个圆形的谷仓，共有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

好，我们的初始化就好了！

那怎么搞呢？

从后往前，找到最前面的空房间，压进去，这里不同于圆形谷仓，我们本来的位置是要留一头牛的，因为第一头牛肯定直接走喜欢的房间，不会向前找空房

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！