# 14116: 【原4116】刀位分配

### 题目描述

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

5 3
1
2
8
4
9

3

# Hint

## 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;
}