11991: 【原1991】为了虫群

题目描述

author: Menghui Wang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1991

题目描述

Jim Raynor率领的人类的部队已经踏上了异虫的基地——查尔星。 作为异虫的首脑，你决定派出爆虫来迎击人类的部队。

样例输入

5 2
-10.0 -6.0 10 11 15


样例输出

2.500000


提示

C++中，下面的程序可以输出保留6位的小数：

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
double f = 1.23;
cout << fixed << setprecision(6) << f << endl;
return 0;
}


BugenZhao's solution

//
// Created by BugenZhao on 2019/3/17.
//
// 二分答案

/*
#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;
int n, k;
double minD = 1e7;

void getAnswer(double *x, double currentD, int pos, int remCircle) {
if (remCircle == 0 && pos != n) return;
if (currentD > minD) return;
if (n - pos < remCircle) return;
if (pos == n) {
minD = min(currentD, minD);
return;
}
for (int i = pos; i < n; ++i) {
getAnswer(x, max(currentD, x[i] - x[pos]), i + 1, remCircle - 1);
}
}

int main() {

cin >> n >> k;
double *x = new double[n]{};
double begin;
cin >> begin;
double tmp;
for (int i = 1; i < n; ++i) {
cin >> tmp;
x[i] = tmp - begin;
}
cout << fixed << setprecision(6) << minD / 2.0 << endl;
return 0;
}
*/

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;
int n, k;
double minD = 1e7;
double *x;

int getRank(int lo, int hi, double num) {
if (hi == lo + 1)
return lo;
int mi = lo + (hi - lo) / 2;
if (x[mi] <= num)
return getRank(mi, hi, num);
else
return getRank(lo, mi, num);
}

int main() {
cin >> n >> k;
x = new double[n]{};
double tmp, begin;
cin >> begin;
for (int i = 1; i < n; ++i) {
scanf("%lf", &tmp);
x[i] = tmp - begin;
}
double min = 0.0, mid, max = x[n - 1];
while (fabs(max - min) >= 1e-7) {
mid = (min + max) / 2;
int curr = 0;
bool flag = false;
for (int i = 0; i < k; ++i) {
curr = getRank(curr, n, x[curr] + mid);
if (curr == n - 1) {
flag = true;
break;
}
++curr;
}
if (flag) max = mid;
else min = mid;
}
cout << fixed << setprecision(6) << mid / 2.0 << endl;
}


FineArtz's solution

/* 为了虫群 */
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

const double INF = 10e7 * 3.0;
double x[100005];
int n, k;

bool check(double p){
int nowl = 1, cnt = 1;
for (int i = 2; i <= n; ++i){
if (x[i] - x[nowl] - 2 * p < 10e-8) continue;
else{
++cnt;
nowl = i;
if (cnt > k) return false;
}
}
return true;
}
int main(){
cin >> n >> k;
for (int i = 1; i <= n; ++i)
cin >> x[i];
double ans = INF, lans = INF;
double l = 0.0, r = x[n] - x[1], m = (l + r) / 2;
while (l - r < 10e-8){
if (check(m)){
lans = ans;
ans = m;
r = m;
if (abs(lans - ans) < 10e-8) break;
}
else l = m;
m = (l + r) / 2;
}
cout << fixed << setprecision(6) << ans << endl;
return 0;
}


ligongzzz's solution

#include "iostream"
#include "cmath"
#include "cstdio"
using namespace std;

constexpr double jd = 1e-7;

double pos[100009] = { 0 };

bool check(double r, int n, int limit) {
int cnt = 1;
for (int i = 0, cur_pos = 0; i < n; ++i) {
if (r < pos[i] - pos[cur_pos]) {
++cnt;
cur_pos = i;
}
if (cnt > limit)
return false;
}
return true;
}

int main() {
int n, k;
scanf("%d %d", &n, &k);

for (int i = 0; i < n; ++i)
scanf("%lf", &pos[i]);

//开始循环
double left = pos[0], right = pos[n - 1];
double r;
while (true) {
auto mid = (right + left) / 2;
r = mid - pos[0];
if (check(r * 2, n, k)) {
right = mid;
if (right - left <= jd) {
printf("%.6f", r);
return 0;
}
}
else {
left = mid;
}
}
return 0;
}


skyzh's solution

#include <iostream>
#include <iomanip>
using namespace std;

double pos[100000];

int main() {
double L = 0, R = 1e8;
int N, K;
scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++) {
scanf("%lf", &pos[i]);
}
while (L < R - 1e-7) {
double M = (L + R) / 2.0;
bool ok = false;
double R_L = pos[0], R_R = R_L + 2.0 * M;
int k = 1;
for (int i = 0; i < N; i++) {
if (pos[i] <= R_R) continue;
R_L = pos[i];
R_R = R_L + 2.0 * M;
++k;
if (k > K) break;
}
if (k <= K) ok = true;
if (ok)
R = M;
else
L = M;
}
cout << fixed << setprecision(6) << R << endl;
return 0;
}


yyong119's solution

#include <cstdio>
#define MAX_N 100010
using namespace std;
const double error = 1e-7;
int n, k;
double a[MAX_N];
bool check(double step_length) {
double start_pos = a[0];
int cnt = 1;
for (register int i = 1; i < n; ++i) {
if (a[i] - start_pos <= step_length) continue;
if ((++cnt) > k) return false;
start_pos = a[i];
}
return true;
}
int main() {
scanf("%d%d", &n, &k);
for (register int i = 0; i < n; ++i) scanf("%lf", &a[i]);
double l = 0, r = a[n - 1] - a[0];
while (r - l > error) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
printf("%.6lf", r / 2);
return 0;
}