点击打开链接poj 3258
思路:二分
分析:
1 题目意思是有一条长度为L的河流,河里有n个石头,现在有奶牛从河的起点0,通过跳跃石头到达终点n+1;现在有一个人,想测掉m个石头,然后求两块石头之间的距离的最小值中的最大值。
2 很明显如果m = 0 , 那么ans就是所有石头间距的最小值min,如果m = n 那么ans就是L ; 现在由于0=<m<=n,所以ans肯定会在[min , L]之间,所以只要在这个区间二分答案,然后找到可以去掉的石头数和m做比较即可
3 如果假设求出删除的石头数为k ,如果k > m ,那么right = mid;如果 k = m , 肯定的是如果另right = mid,那么接下来的k 肯定是小于m的肯定不满足,所以只能left = mid+1 ; 如果k < m ,那么left = mid;
所以有 k > m , right = mid;
k <= m , left = mid+1;
代码:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 50010
int l , n , m;
int dis[MAXN];
int judge(int num){
int count = 0;
int pos = 0;
for(int i = 1 ; i <= n+1 ; i++){
if(dis[i]-dis[pos] <= num)/*求出可以删除的石头数*/
count++;
else
pos = i;
}
return count;
}
void solve(){
int left , right , mid;
sort(dis , dis+n+2);
left = 0x7FFFFFFF;
for(int i = 1 ; i <= n+1 ; i++)
left = min(left , dis[i]-dis[i-1]);
right = l;
if(m == 0){
printf("%d\n" , left);
return;
}
if(m == n){
printf("%d\n" , l);
return;
}
while(left < right){
mid = left + (right-left)/2;
int tmp = judge(mid);
if(tmp > m)
right = mid;
else
left = mid+1;
}
printf("%d\n" , left);
}
int main(){
while(scanf("%d%d%d" , &l , &n , &m) != EOF){
dis[0] = 0;
for(int i = 1 ; i <= n ; i++)
scanf("%d" , &dis[i]);
dis[n+1] = l;
solve();
}
return 0;
}
分享到:
相关推荐
北大POJ3258-River Hopscotch 解题报告+AC代码
poj 3050 Hopscotch.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ2968代码有用,欢迎下载,POJ代码