[LUOGU] P1316 丢瓶盖

题目描述

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

输入输出格式

输入格式：

第一行，两个整数，A,B。（B<=A<=100000）

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

输出格式：

仅一个整数，为所求答案。

输入输出样例

输入样例#1：

5 3

1 2 3 4 5

输出样例#1：

2

说明

限时3秒

终于找到一个心仪的、不容易写错的二分答案模板了，ans在二分中同时保存。

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN=100005;

int n,m;

int a[MAXN];

bool check(long long x){

    int sum=a[1],cnt=1;

    for(int i=2;i<=n;i++){

        if(a[i]-sum>=x) sum=a[i],cnt++;

    }

    return cnt>=m;

}

int main(){

    cin>>n>>m;

    long long l=0,r=1152921504606846976,mid;

    for(int i=1;i<=n;i++) cin>>a[i];

    sort(a+1,a+1+n);

    int ans;

    while(l<=r){

        mid=(l+r)/2;

        if(check(mid)) l=mid+1,ans=mid;

        else r=mid-1;

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

[LUOGU] P1316 丢瓶盖

最新文章

热门文章