poj 2456 Aggressive cows 贪心+二分
2024-09-01 04:25:37
Aggressive cows
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 25944 | Accepted: 11982 |
Description
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).
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
* Line 1: Two space-separated integers: N and C
* Lines 2..N+1: Line i+1 contains an integer stall location, xi
Output
* Line 1: One integer: the largest minimum distance
Sample Input
5 3
1
2
8
4
9
Sample Output
3
Hint
OUTPUT DETAILS:
FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.
Huge input data,scanf is recommended.
题意:有n个位置,m头奶牛,将m头奶牛放到n个位置中,在每一种放置方法中,都有一个两头奶牛之间间隔的最小距离,求在所有放置方法中,这个最小距离的最大值
题解:先确定最小距离的范围是在[ 0 , a[n-1]-a[0] ]之间,用二分查找不断逼近可以放下所有奶牛的最大值
#include<iostream>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
ll a[];
ll n,m;//n是位置数量,m是奶牛数量 int check(ll x)//判断在所有奶牛之中,两两之间的最小距离为x时能否放下所有奶牛
{
ll cnt=,mn=a[];//初始值
for(int i=;i<n;i++)
{
if(a[i]-mn>=x)
{
cnt++;
mn=a[i];//更新
if(cnt==m)
return ;
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n); ll l=,r=a[n-]-a[],mid;//最小距离x一定在[l,r]之间,采用二分查找方法确定x
while(l<=r)
{
mid=l+(r-l)/;
if(check(mid))//当以mid为最小距离能放下所有奶牛时,再增大mid判断能否放下
l=mid+;
else
r=mid-;
}
printf("%d\n",l- );//因为当l>r时退出while循环,所以结果l-1
}
最新文章
- charles工具抓包教程(http跟https)
- 【python之路3】if 语句
- WAMPP安装后mysql无法启动
- 解决拖拽有内容的div的bug和兼容问题
- Python基础2:流程控制语句 while / for循环
- iOS - Swift Range 范围
- (转)android屏幕适配
- 通过文件读写方式实现Matlab和Modelsim的联合仿真
- 靓号正则表达式(前后向查找等) 和 apache正则包使用
- Python 2.7版本与3.6的不同
- 等价于n*n的矩阵,填写0,1,要求每行每列的都有偶数个1 (没有1也是偶数个),问有多少种方法。
- Java核心技术梳理-集合
- Spring IoC的原理为什么是反射而不是new
- Java关系运算
- MegaCli命令使用详解
- 如何搜索IP的地理位置
- Matlab中图像处理实例:灰度变换,空域滤波,频域滤波,傅里叶变换的实现
- C# 图像自动切换
- 云计算时代,传统企业 IT 从业者如何做好转型?
- 文件读取 FILE