poj 3258 跳房子问题 最大化最小值
2024-10-17 16:35:48
题意:奶牛跳房子,从n块石头中移除M块,使得间距最小的最大值?
思路:“转换”
- 从N块中选择n-m块使得两两之间的间距尽可能大
- 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 ;
}
最新文章
- 机器指令翻译成 JavaScript —— No.6 深度优化
- JavaEE Spring
- HDU 5832 A water problem(某水题)
- Mybatis调用Mysql存储过程
- getsockname和getpeername
- linux中ll和du的区别
- 手动书写小代码-foreach实现机制
- C++ 类的前置声明
- C# 汉子增加UTF-8头
- Python中for\while的用法
- 在cmd中运行android.bat报出空指针异常
- 线上平滑升级nginx1.12
- 20175212 《Java程序设计》第2周学习总结
- android studio 编辑markdown文件
- python 生成器和各种推导式
- Confluence 6 XML 备份恢复失败的问题解决
- logstash启动失败的问题追查
- JMS学习以及jms的实现activeMq
- WorldWind源码剖析系列:下载队列类DownloadQueue
- mybatis中的#{}和${}区别
热门文章
- SpringBoot | 第二十三章:日志管理之整合篇
- Docker | 第六章:构建私有仓库
- Servlet的生命周期以及线程安全问题
- vue-实现一个购物车结算页面
- 零基础逆向工程24_C++_01_类_this指针_继承本质_多层继承
- WPF:鼠标长时间无操作,窗口隐藏
- 聊聊javascript的事件
- IOS 进程描述
- Aizu 2301 Sleeping Time(概率,剪枝)
- 2018.6.2 AndroidStudio项目中的问题:===== oast.LENGTH_LONG和Toast.LENGTH_SHORT分别对应多长时间