题目:Problem - C - Codeforces

本题的优解是二分答案,但我其实不会二分,本质是用了两个指针作为边界,然后不断对半缩小范围来快速确定答案。

神奇的二分法

代码:

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

最新文章

  1. CentOS7关闭防火墙方法
  2. [原] Android 自定义View步骤
  3. openwrt: Makefile 框架分析
  4. PHP中echo,print(),print_r()的区别
  5. php 将pdf转成图片且将图片拼接
  6. centos7配置Apache支持HTTPS
  7. sqlmap实例文档
  8. keepalive+nginx 热备跟负载均衡
  9. 【linux】centos6.9安装gearman
  10. linux Bash 常用
  11. tesseract 中文二次训练
  12. [翻译] ASP.NET WebAPI 中的异常处理
  13. PyGreSQL入门,pg模块,pgdb模块
  14. 微信小程序表单校验WxValidate.js使用
  15. 记一次完整的pc前端整站开发
  16. 使用hasOwnProperty监测对象是否含有某个属性
  17. JavaScript的动态特性(通过eval,call,apply和bind来体现)
  18. python安装库(Windows下)
  19. 为什么我要放弃javaScript数据结构与算法(第五章)—— 链表
  20. 学习Pytbon第十天 函数2 内置方法和匿名函数

热门文章

  1. 聊了聊宏内核和微内核,并吹了一波 Linux
  2. VNC服务器的搭建(带图形化支持)
  3. Spring一套全通—工厂
  4. 《手把手教你》系列技巧篇(三十九)-java+ selenium自动化测试-JavaScript的调用执行-上篇(详解教程)
  5. MySQL、Oracle批量插入SQL的通用写法
  6. 从环境搭建到回归神经网络案例,带你掌握Keras
  7. 菜鸡的Java笔记 第三十三 - java 泛型
  8. Tomcat无法启动解决办法
  9. [cf461D]Appleman and Complicated Task
  10. CG Kit探索移动端高性能渲染