The great hero guards the country where Homer lives. The hero has attack power AA and initial health value BB . There are nn monsters in front of the hero. The ii -th monster has attack power a_iai and initial health value b_ibi .
The hero or a monster is said to be living, if his or its health value is positive (greater than or equal to 11 ); and he or it is said to be dead, if his or its health value is non-positive (less than or equal to 00 ).
In order to protect people in the country, the hero will fight with monsters until either the hero is dead or all the monsters are dead.
In each fight, the hero can select an arbitrary living monster and fight with it. Suppose the ii -th monster is selected, and the health values of the hero and the ii -th monster are xx and yy before the fight, respectively. After the fight, the health values of the hero and the ii -th monster become x-a_ix−ai and y-Ay−A , respectively.
Note that the hero can fight the same monster more than once.
For the safety of the people in the country, please tell them whether the great hero can kill all the monsters (even if the great hero himself is dead after killing the last monster).
输入格式
Each test contains multiple test cases. The first line contains tt ( 1 \le t \le 10^51≤t≤105 ) — the number of test cases. Description of the test cases follows.
The first line of each test case contains three integers AA ( 1 \leq A \leq 10^61≤A≤106 ), BB ( 1 \leq B \leq 10^61≤B≤106 ) and nn ( 1 \leq n \leq 10^51≤n≤105 ) — the attack power of the great hero, the initial health value of the great hero, and the number of monsters.
The second line of each test case contains nn integers a_1, a_2, \dots, a_na1,a2,…,an ( 1 \leq a_i \leq 10^61≤ai≤106 ), where a_iai denotes the attack power of the ii -th monster.
The third line of each test case contains nn integers b_1, b_2, \dots, b_nb1,b2,…,bn ( 1 \leq b_i \leq 10^61≤bi≤106 ), where b_ibi denotes the initial health value of the ii -th monster.
It is guaranteed that the sum of nn over all test cases does not exceed 10^5105 .
输出格式
For each test case print the answer: "YES" (without quotes) if the great hero can kill all the monsters. Otherwise, print "NO" (without quotes).
题意翻译
题意
我们定义一个人物为一个二元组 (x,y), 称其中 x 为攻击力, y 为血量. 一个英雄是一个人物. 现在有 n 个怪物, 每个怪物是一个人物. 我们这样定义两个人物 A 与 B 交战:
- A 的血量减少等同于 B 的攻击力的数值, B 的血量也减少等同于 A 的攻击力的数值.
- 然后, A 和 B 中所有血量小于等于 0 的人物死亡.
- 现在英雄需要消灭所有怪物, 消灭怪物的方式是与之交战. 请求出英雄能不能消灭所有的怪物, 即使英雄本人在消灭所有怪物后死亡.
输入格式
第一行包含一个正整数 T(1≤T≤105), 表示有 TT 组测试数据.
接下来第 3k−2 行, 包括第 kk 组数据中, 英雄的攻击力 A (1≤A≤106), 血量 B(1≤B≤106), 怪物个数 n(1≤n≤105).
接下来第 3k−1 行, 包括对于每个 i∈[1,n] 第 k 组数据中第 i 个怪物的攻击力 ai(1≤ai≤106).
接下来第 3k 行, 包括对于每个 i∈[1,n] 第 k 组数据中第 i 个怪物的血量 bi(1≤bi≤106).
所有数据的 n 的总和小于等于 10^5
输出格式
对于每组测试数据, 输出仅一行一个字符串 "YES"(如果英雄能够杀死所有怪物) 或 "NO"(如果英雄不能杀死所有怪物) (不包括括号).
输入输出样例
输入 #1复制
5 3 17 1 2 16 10 999 3 10 20 30 100 50 30 1000 1000 4 200 300 400 500 1000 1000 1000 1000 999 999 1 1000 1000 999 999 1 1000000 999
输出 #1复制
1. YES 2. YES 3. YES 4. NO 5. YES
说明/提示
In the first example: There will be 6 fights between the hero and the only monster. After that, the monster is dead and the health value of the hero becomes 17−6×2=5>0 . So the answer is "YES", and moreover, the hero is still living.
In the second example: After all monsters are dead, the health value of the hero will become 709 regardless of the order of all fights. So the answer is "YES".
In the third example: A possible order is to fight with the 11 -st, 2 -nd, 3 -rd and 44 -th monsters. After all fights, the health value of the hero becomes -400 . Unfortunately, the hero is dead, but all monsters are also dead. So the answer is "YES".
In the fourth example: The hero becomes dead but the monster is still living with health value 1000 - 999 = 1 . So the answer is "NO".
解题思路；
先打血量小、攻击力小的怪物，再打其他的。
注意判断，注意细节。
判断分情况讨论：
当正在打的不是最后一个怪物时，若打完后血量 <=0 则输出NO。- 当正在打的是最后一个怪物时，若打完后血量 + an≤0 则输出
NO。 - 否则输出
YES。
具体实现看ac代码；
#include <iostream> #include <algorithm> #include <cmath> using namespace std; #define ll long long const ll maxn=1e6+7; struct node{ ll a,b; }p[maxn]; bool cmp(node q,node w) { return q.a==w.b?q.b<w.b:q.a<w.a; } int main() { int t; cin>>t; while(t--) { ll A,B,D,n; int b=0; cin>>A>>B>>n;//英雄攻击，血量，怪物个数 for(int i=1;i<=n;i++)cin>>p[i].a;//怪物攻击 for(int i=1;i<=n;i++)cin>>p[i].b;//怪物血量 sort(p+1,p+1+n,cmp);//排序,按照攻击由小到大排，如果攻击相同就按照血量低的排在前面。 for(int i=1;i<=n;i++) { ll C=ceil(1.0*p[i].b/A);//向上取整 就是相当于可以承受英雄多少次攻击 ll D=p[i].a*C;//怪兽攻击英雄的血量 B-=D; if(B<=0&&i<n){//这个意思就是英雄倒下了，但是怪兽还存在 b=1; cout<<"NO"<<endl; break; } if(i==n&&B<0&&B+p[i].a<=0)//英雄到了最后一个怪兽但是自己却没有杀死这个怪兽 , {//第三个式子的意思是英雄其实多被怪兽砍了好几刀，意思就是英雄并没有杀死怪兽 b=1; cout<<"NO"<<endl; break; } } if(!b) cout<<"YES"<<endl; } }
