P1316 丢瓶盖(于答案区间二分查找)

2019/7/21 17:22:23 人评论 次浏览 分类:学习教程

题目描述
陶陶是个贪玩的孩子,他在地上丢了A个瓶盖,为了简化问题,我们可以当作这A个瓶盖丢在一条直线上,现在他想从这些瓶盖里找出B个,使得距离最近的2个距离最大,他想知道,最大可以到多少呢?

输入输出格式
输入格式:
第一行,两个整数,A,B。(B<=A<=100000)

第二行,A个整数,分别为这A个瓶盖坐标。

输出格式:
仅一个整数,为所求答案。

输入输出样例
输入样例#1:
5 3
1 2 3 4 5
输出样例#1:
2

类似的最大值最小化或者最小值最大化问题,通常用二分法就可以很好地解决。我们定义:
设 C(d)表示可以安排瓶盖的位置使得最近的两个瓶盖的距离不小于 d
那么问题就变成了求满足 C(d)的最大的 d,另外,最近的间距不小于 d 也可以说成是所有瓶盖的间距都不小于 d,因此就有 C(d)表示可以安排瓶盖的位置使得任意的两个瓶盖的距离不小于 d。
这个问题的判断使用贪心法便可非常容易地求解。

ac代码
#include<bits/stdc++.h>
typedef long long ll;
typedef double db;
//typedef pair<int,int> pii;
//typedef vector vi;
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7;
const int N = 1e5+20;
#define dep(i,a,b) for(int i=(a);i>=(b);i–)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define mes§ memset(p,0,sizeof§)
using namespace std;
int a,b,l=1e9+7,r,x[N],ans=0;
bool check(int time){
int temp=x[1],ok=1;
rep(i,2,a){
if(x[i]-temp>=time){
ok++;temp=x[i];
}
}
return ok>=b;
}
void find(int lef,int rig){
while(lef<=rig){
int mid=(lef+rig)/2;
if(check(mid)) ans=max(ans,mid),lef=mid+1;
else rig=mid-1;
}
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin>>a>>b;
rep(i,1,a)
cin>>x[i];
sort(x+1,x+1+a);
rep(i,2,a)
l=min(x[i]-x[i-1],l);
r=x[a]-x[1];
find(l,r);
cout<<ans;
return 0;
}

上一篇:AppStore隐私政策网址

下一篇:Kalman滤波

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->