首页 技术 正文
技术 2022年11月23日
0 收藏 604 点赞 4,744 浏览 691 个字

CF1217B

题意:

有一个有 $ x $ 个头的龙,你有 $ n $ 种方案,每种方案中包含你可以砍掉的头 $ d_i $ 和龙会生长的头 $ h_i $

找到一种方案,使得操作数最少。

解法:

考虑贪心,因为没有规定每种方案只能使用一次,所以我们可以记录一个最大的 $ d_i – h_i $ ,每次减去这个值。

又因为如果我们可以一次砍死龙,龙就不会重新复活,所以记录一个 $ d_{max} $ 用于最后的斩杀。

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>using namespace std;#define LL long long
#define N 110int T,n,x,ans,max_d;
int attack,life,max_a;int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&x);
max_a = 0,ans = 0,max_d = 0;
for(int i = 1 ; i <= n ; i++) {
scanf("%d%d",&attack,&life);
max_d = max(max_d,attack - life);
max_a = max(max_a,attack);
}
if(max_a >= x) {
puts("1");
continue;
}
if(max_d <= 0) {
puts("-1");
continue;
}
x -= max_a;
ans = x / max_d + 1;
if(x % max_d) ans++;
printf("%d \n",ans);
}
//system("pause");
return 0;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102