当前位置:网站首页>[牛客] [NOIP2015]跳石头
[牛客] [NOIP2015]跳石头
2022-07-06 17:14:00 【*DDL_GzmBlog】
前言
t a g : tag : tag:二分
二分答案
题意 :
思路 :
因为题目所求的是 最短的最大 ,很标准的一个二分询问方法
因此我们可以考虑二分最短距离,那么我们怎么check呢
很简单,显然对于现在的需要判断的 x,如果两个石头的差小于x的时候 , 我们肯定是要将其移走的
所以我们只需要判断移走的数量和m的关系即可
当然移走的状态我们可以通过last进行转移
code :
int L,n,m;
int a[N];
int i,j;
int b[N];
bool check(int x){
int cnt = 0;
int last = 0 ;
Fup(i,1,n+1){
if(a[i] - last < x) cnt++;
else last = a[i];
if(cnt > m) return false;
}
return true;
}
void solve(){
// cin>>L>>N>>M;
cin>>L>>n>>m;
Fup(i,1,n) cin>>a[i];
a[n+1] = L;
int l = 0 , r = L;
//cout<<ans<<endl;
while(l<=r){
int mid = (l+r)>>1;
if(check(mid)){
l = mid+1;
}
else r = mid - 1;
}
cout<<((l+r)>>1)<<endl;
}
signed main(){
//int t;cin>>t;while(t--)
solve();
return 0 ;
}
边栏推荐
- Part IV: STM32 interrupt control programming
- Advanced learning of MySQL -- basics -- multi table query -- inner join
- 第六篇,STM32脉冲宽度调制(PWM)编程
- [yolov5 6.0 | 6.1 deploy tensorrt to torch serve] environment construction | model transformation | engine model deployment (detailed packet file writing method)
- Model-Free Control
- JS+SVG爱心扩散动画js特效
- Telerik UI 2022 R2 SP1 Retail-Not Crack
- How to get started and improve test development?
- Configuring OSPF basic functions for Huawei devices
- 《安富莱嵌入式周报》第272期:2022.06.27--2022.07.03
猜你喜欢
C9 colleges and universities, doctoral students make a statement of nature!
Configuring OSPF basic functions for Huawei devices
Basic information of mujoco
Linear algebra of deep learning
Lombok 同时使⽤ @Data 和 @Builder 的坑,你中招没?
Part IV: STM32 interrupt control programming
Article management system based on SSM framework
Memory optimization of Amazon memorydb for redis and Amazon elasticache for redis
深度学习之数据处理
[Niuke classic question 01] bit operation
随机推荐
Deep understanding of distributed cache design
【JokerのZYNQ7020】AXI_ EMC。
Advantages and disadvantages of code cloning
Part IV: STM32 interrupt control programming
腾讯云 WebShell 体验
A brief history of deep learning (I)
Matlab learning notes
[C language] dynamic address book
Mongodb client operation (mongorepository)
重上吹麻滩——段芝堂创始人翟立冬游记
第四篇,STM32中断控制编程
通过串口实现printf函数,中断实现串口数据接收
Mujoco finite state machine and trajectory tracking
用tkinter做一个简单图形界面
Chapter 5 DML data operation
深度学习之数据处理
Learning notes 5: ram and ROM
Advanced learning of MySQL -- Fundamentals -- four characteristics of transactions
Leetcode (547) - number of provinces
Stm32f407 ------- SPI communication