Skip to content

14153: 【原4153】捡石子

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4153

Description

一条笔直的公路上有 n 块石子, 没有两块石子在同一个位置. 现在你闲来无事想捡 m 块石子玩, 请问该如何去捡, 才能使捡出的 m 块石子中距离第 k 小的两块石子的距离最大?(k=1 或 2) 请给出这个最大的第 k 小距离.

注意, 这里若有多对石子间的距离都是最小的, 则第二小距离等于最小距离. 例如, 捡出的四块石子的位置分别为 1, 3, 11, 13, 则第二小距离和最小距离一样都是 2.

Input Format

第一行为三个正整数 n, m, k, 分别表示总石子块数, 想捡的石子块数, 所求的是最小还是第二小距离的最大值;

第二行有 n 个整数, 表示 n 块石子的位置.

Output Format

一行, 一个正整数, 表示最大的第 k 小距离.

Sample Input

5 3 2
1 2 3 4 6

Sample Output

4

Hint

-10^8<=每块石子的位置<=10^8

3<=m<=n<=10^5

ligongzzz's solution

#include "iostream"
#include "algorithm"
using namespace std;

//记录被选中的点
int choose[100009] = { 0 };

int main() {
    int n, m, k;
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;

    int *dis = new int[n];
    for (int i = 0; i < n; i++)
        cin >> dis[i];
    sort(dis, dis + n);
    if (k == 1) {
        int cl = 0, cr = dis[n - 1],ans=0;
        //二分法
        while (cl <= cr) {
            int mid = (cl + cr) >> 1,cnt=0;
            for (int i = 1, startNum = 0; i < n; i++)
                if (dis[i] - dis[startNum] < mid) cnt++;
                else startNum = i;
            if (cnt > n - m) cr = mid - 1;
            else {
                cl = mid + 1;
                ans = mid;
            }
        }
        cout << ans;
    }
    else if(k==2){
        int cl = dis[0], cr = 2*dis[n - 1]-3*dis[0], ans = 0;
        //二分法
        while (cl <= cr) {
            int mid = (cl + cr) >> 1, cnt = 0,topNum=0;
            choose[topNum++] = 0;
            bool flag = false;
            for (int i = 1, startNum = 0; i < n; i++)
                if (dis[i] - dis[startNum] < mid) { 
                    cnt++; 
                    //判断是否在末尾
                    if (i == n - 1) {
                        choose[topNum - 1] = i;
                    }
                }
                else {
                    choose[topNum++] = i;
                    startNum = i;
                }
            //判断是否可以插入
            for (int i = 1; i < topNum; i++) {
                if (choose[i] > choose[i - 1] + 1) {
                    if (dis[choose[i] - 1] - dis[choose[i - 1]] >= mid ||
                        dis[choose[i]] - dis[choose[i - 1] + 1] >= mid) {
                        flag = true;
                        break;
                    }
                }
            }
            if (cnt < n - m + 1)
                flag = true;
            if (cnt > n - m + 1||!flag) 
                cr = mid - 1;
            else {
                cl = mid + 1;
                ans = mid;
            }
        }
        cout << ans;
    }

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 100000 + 100;
int n, m, k;
long long l, r, mid, ans, pos[maxN];
bool stone[maxN];

void qSort(long long *, int, int);
bool judge(long long);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
        cin >> pos[i];
    }
    qSort(pos, 0, n - 1);

    if (pos[0] < 0) {
        for (int i = n - 1; i >= 0; i--) {
            pos[i] -= pos[0];
        }
    }

    l = pos[0];
    r = pos[n - 1];

    while (l <= r) {
        mid = (l + r) / 2;
        if (judge(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans;

    return 0;
}

void qSort(long long *num, int l, int h) {
    if (l >= h) {
        return;
    }
    int first = l, last = h;
    long long key = num[first];

    while (first < last) {
        while (first < last && num[last] >= key) {
            --last;
        }
        num[first] = num[last];
        while (first < last && num[first] <= key) {
            ++first;
        }
        num[last] = num[first];
    }
    num[first] = key;
    qSort(num, l, first - 1);
    qSort(num, first + 1, h);
}

bool judge(long long x) {
    if (k == 1) {
        int sum = n - m, now = 0;

        for (int i = 1; i < n - 1; i++) {
            if (pos[i] - pos[now] < x) {
                sum--;
                if (sum < 0) {
                    return 0;
                }
            } else {
                now = i;
            }
        }

        if (pos[n - 1] - pos[now] < x && sum == 0) {
            return 0;
        } else {
            return 1;
        }
    } else {
        int sum = n - m + 1, now = 0;
        for (int i = 0; i < n; i++) {
            stone[i] = 1;
        }

        for (int i = 1; i < n - 1; i++) {
            if (pos[i] - pos[now] < x) {
                sum--;
                stone[i] = 0;
                if (sum < 0) {
                    return 0;
                }
            } else {
                now = i;
            }
        }

        if (pos[n - 1] - pos[now] < x) {
            sum--;
        }
        if (sum > 0) {
            return 1;
        } else if (sum < 0) {
            return 0;
        } else {
            stone[now] = 0;
        }

        int l, r;
        for (int i = 1; i < n - 1; i++) {
            if (stone[i] == 1) {
                continue;
            } else {
                l = i;
                r = i;
                while (stone[l] == 0 && l >= 0) {
                    l--;
                }
                while (stone[r] == 0 && r < n) {
                    r++;
                }

                if (((pos[r] - pos[i]) >= x) || ((pos[i] - pos[l]) >= x)) {
                    return 1;
                }
            }
        }
        return 0;
    }
}

WashSwang's solution

#include <iostream>
#include <algorithm>
using namespace std;
int l,r,m,n,k,a[200000],mid,ans;
bool test(int x){
    int now=a[0],len=1;
    if (k==1){
        for (int i=1;i<n;++i)
            if (a[i]-now>=x) {
                now=a[i];
                len++;
                if (len>=m) return true;
            }
        return false;
    }
    else{
        int p[200000],q[200000];
        p[0]=1;
        for (int i=1;i<n;++i) {
            if (a[i] - now >= x) {
                now = a[i];
                len++;
                p[i] = len;
            } else p[i] = p[i - 1];
        }
        if (p[n-1]>=m) return true;
        now=a[n-1];
        q[n-1]=1;
        len=1;
        for (int i=n-2;i>=0;--i){
            if (now-a[i]>=x) {
                now=a[i];
                len++;
                q[i]=len;
            }
            else q[i]=q[i+1];
            if (p[i]+q[i+1]>=m) return true;
        }
        if (q[0]>=m) return true;
        return false;
    }
}
int main() {
    cin>>n>>m>>k;
    for (int i=0;i<n;++i)
        cin>>a[i];
    sort(a,a+n);
    l=0;
    r=2000000000;
    while (l<=r)
    {
        mid=(r-l)/2+l;
        if (test(mid)){
            if (mid>ans) ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4153.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, k;
int a[100005], f[100005], g[100005];
void init(){
    n = read(), m = read(), k = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    sort(a + 1, a + n + 1);
}
void solve(){
    int l = 0, r = 100000001;
    while (r > l){
        int mid = (l + r + 1) >> 1;
        f[0] = 0;
        for (int i = 1, cur = 0; i <= n; ++i){
            while (cur < i - 1 && a[i] - a[cur + 1] >= mid)
                ++cur;
            f[i] = f[cur] + 1;
        }
        g[n + 1] = 0;
        for (int i = n, cur = n + 1; i >= 1; --i){
            while (cur > i + 1 && a[cur - 1] - a[i] >= mid)
                --cur;
            g[i] = g[cur] + 1;
        }
        bool flag = false;
        if (k == 2){
            for (int i = 1; i <= n + 1; ++i){
                if (f[i - 1] + g[i] >= m){
                    flag = true;
                    break;
                }
            }
        }else{
            flag = g[1] >= m;
        }
        if (flag) l = mid;
        else r = mid - 1;
    }
    printf("%d\n", l);
}
int main(){
    init();
    solve();
    return 0;
}