【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; }