POJ 2456 编程技巧之------二分查找思想的巧妙应用
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 18599 | Accepted: 8841 |
Description
His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Input
* Lines 2..N+1: Line i+1 contains an integer stall location, xi
Output
Sample Input
5 3
1
2
8
4
9
Sample Output
3
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define INF 999999999
const int MAX_N=100005;
int N,M;
int x[MAX_N];
//判断是否满足条件
bool C(int d)
{
int last=0;
for(int i=1;i<M;i++)
{
int crt=last+1;
while(crt<N&&x[crt]-x[last]<d)
{
crt++;
}
if(crt==N)return false;
last = crt;
}
return true;
}
void solve()
{
sort(x,x+N);
int lb=0,ub=INF;
int mid;
while(ub-lb>1)
{
mid=(lb+ub)/2;
if(C(mid))lb=mid;
else ub=mid;
}
printf("%d\n",lb);
}
int main()
{
//freopen("C://Users/Administrator/Desktop/acm.txt","r",stdin);
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++)
{
scanf("%d",&x[i]);
}
solve();
return 0;
}
最新文章
- 【原】tomcat 7 启动报错:java.lang.NoSuchMethodError: javax.servlet.ServletContext.getSessionCookieConfig()Ljavax/servlet/SessionCookieConfig的解决
- SPOJ - PLSQUARE Palin Squar(hash+回文串)
- 给flash添加A链接
- SweetAlert – 替代 Alert 的漂亮的提示效果
- [JAVA教程] 2016年最新spring4框架搭建视频教程 【尚学堂】
- C++Socket编程总结 [转]
- IDEA 编译时报错 “未结束的字符串文字” “解析时已经达到文件结尾”
- IE浏览器打开f12才正常
- 名词释义(ActiveMQ 和 Webservice)
- sublime text常用插件
- web前端笔试题
- (转)solr排序OOM解决方法
- CSS-div漂浮
- css 实现页面加载中等待效果
- Lucene文件扩展名
- Mac上使用jenkins+ant执行第一个程序
- Python基础之字符串拼接简单介绍
- <;转>;jmeter(二十三)分布式测试
- Kiss MySQL goodbye for development and say hello to HSQLDB
- [Shell]Bash基本功能:通配符与特殊符号