原题链接:http://codeforces.com/contest/1153/problem/A
题目原文:
A. Serval and Bus
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
It is raining heavily. But this is the first day for Serval, who just became 3 years old, to go to the kindergarten. Unfortunately, he lives far from kindergarten, and his father is too busy to drive him there. The only choice for this poor little boy is to wait for a bus on this rainy day. Under such circumstances, the poor boy will use the first bus he sees no matter where it goes. If several buses come at the same time, he will choose one randomly.
Serval will go to the bus station at time tt, and there are nn bus routes which stop at this station. For the ii-th bus route, the first bus arrives at time sisi minutes, and each bus of this route comes didi minutes later than the previous one.
As Serval's best friend, you wonder which bus route will he get on. If several buses arrive at the same time, you can print any of them.
Input
The first line contains two space-separated integers nn and tt (1≤n≤1001≤n≤100, 1≤t≤1051≤t≤105) — the number of bus routes and the time Serval goes to the station.
Each of the next nn lines contains two space-separated integers sisi and didi (1≤si,di≤1051≤si,di≤105) — the time when the first bus of this route arrives and the interval between two buses of this route.
Output
Print one number — what bus route Serval will use. If there are several possible answers, you can print any of them.
Examples
input
Copy
2 2
6 4
9 5
output
Copy
1
input
Copy
5 5
3 3
2 5
5 6
4 9
6 1
output
Copy
3
input
Copy
3 7
2 2
2 3
2 4
output
Copy
1
Note
In the first example, the first bus of the first route arrives at time 66, and the first bus of the second route arrives at time 99, so the first route is the answer.
In the second example, a bus of the third route arrives at time 55, so it is the answer.
In the third example, buses of the first route come at times 22, 44, 66, 88, and so fourth, buses of the second route come at times 22, 55, 88, and so fourth and buses of the third route come at times 22, 66, 1010, and so on, so 11 and 22 are both acceptable answers while 33 is not.
题目大意:
Serval要去公交站台,已知 t min 到达站台,n班公交车,a min 时到达站台,之后每 b min 一辆,Serval每次到站后选择第一辆公交乘坐,问是第几辆。
解题思路:
对应的每一班只要求出等待时间即可,暴力法可以过,但仔细想想,其实通过简单的除余方法就可算出,毕竟每 b min 一辆车很容易让人想到跟MOD有关。
if (t > a) wait = ((a - t) % b + b) % b;
else wait = a - t;
这里一个负数除余为正的技巧 ((-x) % MOD + MOD) % MOD
AC代码:
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
int n, t, i, minv, minid, a, b, v;
while (scanf("%d%d", &n, &t) != EOF)
{
minid = INF;
minv = INF;
for (i = 1; i <= n; i++)
{
scanf("%d%d", &a, &b);
if (t > a) v = ((a - t) % b + b) % b;
else v = a - t;
// printf("%d\n", v);
if (v < minv)
{
minv = v;
minid = i;
}
}
printf("%d\n", minid);
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)