Skip to content

14116: 【原4116】刀位分配

题目

题目描述

author: 狐之助 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4116

Description

审神者最近得到了一大笔小判，用这些小判扩建了一下刀位（这些刀位从左到右排成一条直线，每个刀位在一个坐标点x上(0 <=x<=1,000,000,000），用来放她心爱的刀剑们。但是不知道为什么，最近发生了一件怪事。如果把两把刀放在一起，那么一到晚上，就会听到两个人说话的声音，这让还是一个小女孩的审神者觉得很害怕，于是她决定每个刀位只放一把刀，并且两把刀的间距越远越好。

已知审神者现在一共有N (2 <= N <= 100,000)个刀位和S (2 <= S <=N)把刀。她想给定一种放置刀剑的方法，使得每两把刀的最短距离越大越好。请写一个程序帮助这个小女孩，让她知道最大的最短距离是多少吧！

Input Format

第一行：两个用空格隔开的数字，分别代表N和C

第二到第N+1行：每行一个数字，代表刀位的坐标

Output Format

一个数字，代表最大的最短距离

Sample Input

5 3
1
2
8
4
9

Sample Output

3

Hint

审神者可以把这三把刀分别放在1,4，8的位置。

BugenZhao's solution 

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

int n, s;
int *x;

bool check(int d) {
    int count = 1, lastPos = 0;
    for (int i = 1; i < n; ++i) {
        if (x[i] - lastPos >= d) {
            ++count;
            lastPos = x[i];
        }
    }
    return count >= s;
}

int main() {
    cin >> n >> s;
    x = new int[n]{};
    for (int i = 0; i < n; ++i) {
        scanf("%d", x + i);
    }
    sort(x, x + n);
    int tmp = x[0];
    for (int i = 0; i < n; ++i) {
        x[i] -= tmp;
    }
    int min = 0, mid, max = x[n - 1];
    while (min <= max) {
        mid = (min + max) / 2;
        if (check(mid)) min = mid + 1;
        else max = mid - 1;
    }
    cout << max << endl;
}

FineArtz's solution 

/* 刀位分配 */
#include <iostream>
using namespace std;

int n, s;
int a[100005];

void qsort(int l, int r){
    int i = l, j = r;
    int mid = a[(i + j) / 2];
    while (i <= j){
        while (a[i] < mid)
            ++i;
        while (a[j] > mid)
            --j;
        if (i <= j){
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
            ++i;
            --j;
        }
    }
    if (i < r)
        qsort(i, r);
    if (j > l)
        qsort(l, j);
}

bool check(int ans){
    int i = 1, j = 2, t = s - 1;
    while (j <= n){
        if (a[j] - a[i] >= ans){
            --t;
            i = j;
        }
        if (t == 0)
            return true;
        ++j;
    }
    return false;
}

int main(){
    cin >> n >> s;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    qsort(1, n);
    int l = 1, r = a[n] - a[1], mid;
    while (l < r){
        mid = (l + r) / 2 + (l + r) % 2;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

ligongzzz's solution 

#include "iostream"
using namespace std;

template <class T, class T_val = decltype(*declval<T>()),
    class Compare = bool (*)(T_val, T_val)>
    void quick_sort(T start, T end,
        Compare cmp = [](T_val a, T_val b) {return a < b; }) {
    if (start == end)
        return;
    auto i = start, j = end;
    --j;
    if (i == j)
        return;
    //交换
    auto key = *start;
    for (bool status = true; i != j;) {
        if (status) {
            if (cmp(*j, key)) {
                *i = *j;
                ++i;
                status = false;
            }
            else
                --j;
        }
        else {
            if (cmp(key, *i)) {
                *j = *i;
                --j;
                status = true;
            }
            else
                ++i;
        }
    }
    *i = key;
    //递归
    quick_sort(start, ++i, cmp);
    quick_sort(i, end, cmp);
}

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

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

    int* dis = new int[n];
    for (int i = 0; i < n; i++)
        cin >> dis[i];
    quick_sort(dis, dis + n);
    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;


    return 0;
}

q4x3's solution 

/**
 * 排序 + 二分
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
    T* A = a + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    T* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    T* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
    if(hi - lo < 2) return;
    int mi = (lo + hi) / 2;
    mergeSort(lo, mi, A); mergeSort(mi, hi, A);
    merge(lo, mi, hi, A);
}

int N, C, pos[100233];

bool check(int dis) {
    int cnt = 1, cur = 0;
    for(int i = 1; i < N;++ i) {
        if(pos[i] - pos[cur] >= dis) {
            ++ cnt;
            cur = i;
            if(cnt >= C) return 1;
        }
    }
    return 0;
}

int main() {
    scanf("%d%d", &N, &C);
    for(int i = 0;i < N;++ i) {
        scanf("%d", &pos[i]);
    }
    mergeSort(0, N, pos);
    int lo = 0, hi = 1e9 + 10;
    while(lo <= hi) {
        int mi = (lo + hi) / 2;
        if(check(mi)) {
            lo = mi + 1;
        } else {
            hi = mi - 1;
        }
    }
    cout << lo << endl;
}

skyzh's solution

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int L = 0, R = 1e9 + 2;
    int pos[100000];
    int N, S;
    scanf("%d%d", &N, &S);
    for (int i = 0; i < N; i++) scanf("%d", &pos[i]);
    int M = 0;
    sort(pos, pos + N);
    while (L < R) {
        M = (L + R + 1) / 2;
        int next_pos = 0, s = 0;
        for (int i = 0; i < N; i++) {
            if (pos[i] >= next_pos) {
                ++s;
                next_pos = pos[i] + M;
            }
        }
        if (s >= S) L = M;
        else R = M - 1;
    }
    printf("%d\n", L);
    return 0;
}

victrid's solution 

#include <cstring>
#include <iostream>
using namespace std;
//binary answer
int* MergeSort(int* list, int listSize) {
    if (listSize == 1)
        return list;
    if (listSize == 2) {
        if (list[0] > list[1]) {
            int temp = list[0];
            list[0]  = list[1];
            list[1]  = temp;
            return list;
        }
        return list;
    }
    int* tmplist = new int[listSize];
    int* llst    = MergeSort(list, listSize / 2);
    int* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
    int lct = 0, rct = 0;
    while (lct + rct != listSize) {
        if ((llst[lct] <= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
            tmplist[lct + rct] = llst[lct];
            lct++;
        } else {
            tmplist[lct + rct] = rlst[rct];
            rct++;
        }
    }
    memcpy(list, tmplist, sizeof(int) * listSize);
    delete[] tmplist;
    return list;
}
int place[100000], place_count, knife_count;
bool check(int mind) {
    int i = 0, total = 0;
    for (int j = 0; j < place_count; j++) {
        if (place[j] - place[i] >= mind) {
            i = j;
            total++;
            if (total == knife_count - 1)
                return 1;
        }
    }
    return 0;
};
int main() {
    cin >> place_count >> knife_count;
    for (int i = place_count; i > 0; i--) {
        scanf("%d", place + i - 1);
    }
    MergeSort(place, place_count);
    int l = 0,
        r = place[place_count - 1];
    while (l < r) {
        if (check((l + r + 1) / 2))
            l = (l + r + 1) / 2;
        else
            r = (l + r - 1) / 2;
    }
    cout << l;
    return 0;
}

yyong119's solution 

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 100010;
int pos[MAX_N];
int n, s;

int main() {
    scanf("%d%d", &n, &s);
    for (int i = 0; i < n; ++i) scanf("%d", &pos[i]);
    sort(pos, pos + n);
    int l = 1, r = 1000000000;
    while (l < r - 3) {
        int mid = (l + r) >> 1, cnt = 1, p = 0, flag = 0;
        for (int i = 1; i < n; ++i)
            if (pos[i] - pos[p] >= mid) {
                ++cnt; p = i;
                if (cnt >= s) {
                    flag = 1; break;
                }
            }
        if (flag) l = mid;
        else r = mid - 1;
    }
    int k;
    for (k = r; k >= l; --k) {
        int cnt = 1, p = 0;
        for (int i = 1; i < n; ++i)
            if (pos[i] - pos[p] >= k) {
                ++cnt; p = i;
            }
        if (cnt >= s) break;
    }
    printf("%d\n", k);
    return 0;
}