【二分答案】CF1613 C. Poisoned Dagger
2024-09-06 08:36:35
本题的优解是二分答案,但我其实不会二分,本质是用了两个指针作为边界,然后不断对半缩小范围来快速确定答案。
神奇的二分法
代码:
#include <iostream>
using namespace std;
typedef long long ll;
ll a[110];
ll n, h;
bool check(ll k)
{
ll t = h - k;
for (int i = 2; i <= n; ++i)
{
t -= min(k, a[i] - a[i - 1]);
}
if (t <= 0)
return 1;
else
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
cin >> n >> h;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
ll l = 1, r = h;
while (l <= r)
{
ll mid = (l + r) >> 1;//取中点
if (check(mid))
{
r = mid - 1;
}
else
l = mid + 1;
}
cout << l << endl;
}
return 0;
}
最新文章
- CentOS7关闭防火墙方法
- [原] Android 自定义View步骤
- openwrt: Makefile 框架分析
- PHP中echo,print(),print_r()的区别
- php 将pdf转成图片且将图片拼接
- centos7配置Apache支持HTTPS
- sqlmap实例文档
- keepalive+nginx 热备跟负载均衡
- 【linux】centos6.9安装gearman
- linux Bash 常用
- tesseract 中文二次训练
- [翻译] ASP.NET WebAPI 中的异常处理
- PyGreSQL入门,pg模块,pgdb模块
- 微信小程序表单校验WxValidate.js使用
- 记一次完整的pc前端整站开发
- 使用hasOwnProperty监测对象是否含有某个属性
- JavaScript的动态特性(通过eval,call,apply和bind来体现)
- python安装库(Windows下)
- 为什么我要放弃javaScript数据结构与算法(第五章)—— 链表
- 学习Pytbon第十天 函数2 内置方法和匿名函数