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