问题标题: 酷町堂：4559 好斗的**

Question

0

已解决

汪宇航

新手启示者

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
bool ch(int mid){
    int p=1;
    int c=1;
    for(int i=2;i<=n;i++){
        if(a[i]-p>=mid){
            c++;
            p=a[i];
        }
    }
    return c>=m;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n);
    int l=1,r=a[n]-a[1];
    while(l<r){
        int mid=(l+r+1)/2;
        if(ch(mid)){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    cout<<l;
    return 0;
}

WA80，错误点#3&#10

汪宇航在2021-09-19 10:54:34追加了内容

额，**=”ji“

酷町豆刷题求解 C++ 1条评论 4 年，6 月前

Answer 1

已采纳

王文博

缔造者之神

bool check(int mid)
{
    int cnt=1,pos=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i]-a[pos]>=mid)
        {
            cnt++;
            pos=i;
        }
        if(cnt>=m) return true;
    }
    return false;
}

Answer 2

李奕歌

初级天翼

核心：

long long a[100861];
bool judge(int n,long long mid,int c){
    int count = 1;
    long long t=a[0];
    for (int i=1;i<n;i++){
        if (a[i]-t>=mid){
            count++;
            t=a[i];
            if (count>=c)
                return true;
        }
    }
    return false;
}


int n,c;
while (~scanf("%d%d",&n,&c)){
    for (int i=0;i<n;i++)
        cin >> a[i];
    sort(a,a+n);
    long long left =0;
    long long right=a[n-1]-a[0];
    while (left<right){
        long long mid=(left+right)/2;
        if (judge(n,mid,c))
            left=mid+1;
        else
            right=mid;
    }
    cout << left-1 << endl;
}

问题标题: 酷町堂：4559 好斗的**

2 个回答: