【C++ 二分】电脑游戏

题目描述

小明在玩电脑游戏。游戏中总共有q个关卡。每个关卡的开始，他都会有k滴血，初始得分0分，他需要抵抗n波怪物攻击，如果最终玩家的血量严格大于0滴则为胜利（等于0滴也不算胜利）。每波怪物攻击共有两种，第一种攻击是扣a滴血，但可以加1分，第二种攻击是扣b滴血(b<a)，不能获得分数。现在，他想知道每一关是不是能玩出来（每一关共有n波攻击，对于每一波攻击，他要么选择抵抗第一种要么选择抵抗第二种，也就是说每次攻击他必须要选择承受抵抗一种，因为逃不掉），在每一关中如果能获得胜利则输出最大的得分，如果不可以则输出-1。
由于关卡太多了，所以他想请你来帮助他。

输入

第一行输入一个整数q（1≤q≤105），表示一共的关卡数。
下面q行表示q个关卡，每个关卡包含四个整数k，n，a和b（1≤k，n≤109,1≤b<a≤109），分别表示初始时的血量，该关卡中怪物要攻击的次数，每次攻击的2种情况。

输出

对于每个关卡，请输出一个整数。如果乐乐无法获得胜利则输出-1，如果乐乐可以胜利则输出最大的得分数。

样例输入 Copy

6
15 5 3 2
15 5 4 3
15 5 2 1
15 5 5 1
16 7 5 2
20 5 7 3

样例输出 Copy

4
-1
5
2
0
1

提示

在第一关中，乐乐在前4波攻击中选择抵抗a种攻击，获得4分，在第5波攻击中选择抵抗b种攻击，不得分，最后乐乐还有1滴血，并得4分。
在第二关中，乐乐无法完成游戏，虽然一开始有15滴血，算是他每次抵抗最弱的b=3的攻击，也需要少15滴血，最后血量变为0。

#include <iostream>
using namespace std;
int k, n, a, b;
bool ck(long long x)
{
	if (x * a + (n - x) * b >= k) return 0;
	return 1;
}
int main()
{
	int q;
	scanf("%d", &q);
	while (q--)
	{
		scanf("%d%d%d%d", &k, &n, &a, &b);
		if (b * n >= k)
		{
			printf("-1\n");
			continue;
		}
		long long L = -1, R = n + 1;
		while (L + 1 != R)
		{
			long long mid = (L + R) >> 1;
			if (ck(mid)) L = mid;
			else R = mid;
		}
		printf("%lld\n", L);
	}
	return 0;
}