题意:奶牛跳房子,从n块石头中移除M块,使得间距最小的最大值?
思路:“转换”

  1. 从N块中选择n-m块使得两两之间的间距尽可能大
  2. c(d) 是间距最大的满足条件,即第一块 放在 xi的位置 下一块就要放在 xj-xi>=d的位置

解决问题的代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int x[];
int l, n, m;
bool solve(int d)
{
int last = ;
for (int i = ; i < n - m; i++)
{
int cur = last + ;
while (cur < n&&x[cur] - x[last] < d)
{
cur++;
}
if (cur == n) return false;
last = cur;
}
return true;
}
int main()
{
scanf("%d%d%d", &l, &n, &m);
for (int i = ; i <= n; i++)
scanf("%d", &x[i]);
++n;
x[n] = l;
++n;
sort(x, x + n);
int lb = , ub = l + ;
while (ub - lb > )
{
int mid = (ub + lb) / ;
if (solve(mid)) lb = mid;
else ub = mid;
}
printf("%d\n", lb);
return ;
}

最新文章

  1. 机器指令翻译成 JavaScript —— No.6 深度优化
  2. JavaEE Spring
  3. HDU 5832 A water problem(某水题)
  4. Mybatis调用Mysql存储过程
  5. getsockname和getpeername
  6. linux中ll和du的区别
  7. 手动书写小代码-foreach实现机制
  8. C++ 类的前置声明
  9. C# 汉子增加UTF-8头
  10. Python中for\while的用法
  11. 在cmd中运行android.bat报出空指针异常
  12. 线上平滑升级nginx1.12
  13. 20175212 《Java程序设计》第2周学习总结
  14. android studio 编辑markdown文件
  15. python 生成器和各种推导式
  16. Confluence 6 XML 备份恢复失败的问题解决
  17. logstash启动失败的问题追查
  18. JMS学习以及jms的实现activeMq
  19. WorldWind源码剖析系列:下载队列类DownloadQueue
  20. mybatis中的#{}和${}区别

热门文章

  1. SpringBoot | 第二十三章:日志管理之整合篇
  2. Docker | 第六章:构建私有仓库
  3. Servlet的生命周期以及线程安全问题
  4. vue-实现一个购物车结算页面
  5. 零基础逆向工程24_C++_01_类_this指针_继承本质_多层继承
  6. WPF:鼠标长时间无操作,窗口隐藏
  7. 聊聊javascript的事件
  8. IOS 进程描述
  9. Aizu 2301 Sleeping Time(概率,剪枝)
  10. 2018.6.2 AndroidStudio项目中的问题:===== oast.LENGTH_LONG和Toast.LENGTH_SHORT分别对应多长时间