F: Rabbit的郊游之旅
F: Rabbit的郊游之旅
内存限制：128 MB时间限制：30 S标准输入输出
题目描述
Rabbit 考研结束后相约与同学去郊游。他们想尽快到达目的地，但是有的人走得快有的人走得慢，这让 Rabbit 很苦恼。
不过好在 Rabbit 能够对走得比较慢的人施展魔法。
假设第 i 个人的步行速度为 vi 米/分钟，对他施展魔法之后能让他的速度变为 wi 米/分钟。
现在 Rabbit 想知道他们最快能在第几分钟全部达到目的地。
注:一分钟只能施展一次魔法，且持续时间为一分钟。
输入格式
输入数据第一行为 T，表示数据组数。(1<=T<=10)
每组数据第一行为两个整数 N，S，分别表示学生总数和距离目的地的距离。(1<=N,S<=10^5)
接下来 N 行，第 i 行有两个整数 vi，wi。(1<=vi<=wi<=10^5)
输出格式
对于每组数据输出一个整数，表示最快能在第几分钟全部达到目的地，占一行。
输入样例 复制
1
3 9
5 10
2 4
3 7
输出样例 复制
3
思路：二分答案暴力判断
代码：
#include <iostream>
using namespace std;
int v[100005], w[100005], runTime[100005];
int n, s;
int isRight(int value)
{
int temp = 0;
for (int i = 0; i < n; i++)
{
if (runTime[i] <= value)
continue;
int c = w[i] - v[i];
if (c == 0)
return 0;
int diff = s - value * v[i];
while (diff > 0)
{
temp++;
diff -= c;
}
if (temp > value)
return 0;
}
return 1;
}
int main()
{
int a;
cin >> a;
while (a--)
{
cin >> n >> s;
for (int i = 0; i < n; i++)
{
cin >> v[i] >> w[i];
runTime[i] = s / v[i];
if (s % v[i] != 0)
runTime[i]++;
}
int l = 0, r = 1E6;
while (l < r)
{
int mid = (l + r) / 2;
if (isRight(mid))
r = mid;
else
l = mid + 1;
}
cout << r << endl;
}
return 0;
}
评论