【2020.02.01NOIP普及模拟4】怪兽
题目描述
PYWBKTDA最近正在打怪兽,一个斯拉夫神话中的凶猛怪兽,一个有着多个头的巨大龙状爬行动物。
开始的时候,怪兽有X个头,你有n种打击方式。如果你选择第i种打击方式,这个神奇的怪兽会减 少min(d i
,cur)个头。这里cur表示当前怪兽拥有的头的数量。但是如果怪兽被打击以后还至少留下 了一个头,那么它就会再长出h i 个头来。当cur
= 0或者小于0的时候,怪兽被打败了。 注意,你可以使用任何一种打击方式任何次数,以任何的顺序。 例如,如果当前cur = 10,d = 7,h = 10,那么一次打击以后怪兽就会有13个头了（因为减少了7个 头以后,怪兽还剩下3个头,再加上10个头）。但是如果当前cur =
10,d = 11,h = 100,那么怪兽就被打败了。
输入
第一行输入是两个整数n和x,分别表示打击的种类和开始时候怪兽的头的数量。
接下来n行, 每行两个整数描述了d i 和h i ,表示第i种打击减少的头的数量和会长出来的头的数量。
输出
输出只有一个整数,表示最少需要打击的次数,如果怪兽无法被打败,就输出−1。
输入输出样例
【输入样例1】
3 10 6 3 8 2 1 4
【输出样例1】
2
【输入样例2】
4 10
4 1
3 2
2 6
1 100
【输出样例2】
3
【输入样例3】
2 15
10 11
14 100
【输出样例3】
-1
数据范围限制
对于50%的数据,1 ≤ n ≤ 10,1 ≤ x ≤ 100,1 ≤ d i ≤ 100,1 ≤ h i ≤ 100。
对于100%的数据,1 ≤ n ≤ 100,1 ≤ x ≤ 10 9 ,1 ≤ d i ≤ 10 9 ,1 ≤ h i ≤ 10 9 。
提示
样例1，你可以使用第一种打击方式,第一次打击以后剩下(10-6+3=7)个头,再进行第2次打击。
样例2，你可以使用第一种打击方式,攻击3次。
样例3，这里你无法打败怪兽。
解析
这道题数据挺水的，直接暴力。
code
#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
//freopen("monster.in","r",stdin);
//freopen("monster.out","w",stdout);
int n,x,y,t[105],d[105],h[105],ans=0;
scanf("%d%d",&n,&x);
for(int i=1;i<=n;++i){
scanf("%d%d",&d[i],&h[i]);
t[i]=d[i]-h[i];
}
while(x){
int fff=false;
for(int i=1;i<=n;++i){
if(x-d[i]<=0){
ans++;
fff=true;
break;
}
}
if(fff)break;
int maxx=-999999999;
for(int i=1;i<=n;++i){
if(maxx<t[i])maxx=t[i];
}
int xi=x;
if(maxx!=-999999999){
ans++;
x-=maxx;
if(x>=xi){
printf("-1");
return 0;
}
}
}
printf("%d",ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}