11991: 【原1991】为了虫群

题目

题目描述

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

题目描述

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

爆虫身上长有充满酸液的囊。 当它接近敌人时，会触发体内的不稳定化学物质进行反应，将自身引爆，向外泼洒强酸。 自爆会摧毁爆虫，但同时也会对半径\(R\)之内(包括距离为\(R\)的点)的敌人造成大量伤害。

你观察到，人类有\(n\)名陆战队员，站成一条直线。 每个陆战队员的坐标是\(x_i\)。 你有\(k\)个爆虫。 爆虫的酸液会对陆战队员造成巨大伤害，将其瞬间消灭。 你可以把每只爆虫安排在直线上的任意位置，然后引爆，从而消灭距离该爆虫不超过\(R\)的所有陆战队员。

为了消灭所有\(n\)个陆战队员，你需要计算，爆虫的爆炸半径\(R\)至少要多少。

输入格式

输入共两行。

第一行是用空格隔开的两个整数，\(n\)和\(k\)。\(1 \leq k < n \leq 100,000\)。

第二行是用空格隔开的\(n\)个实数，表示每个陆战队员的坐标\(x_i\)。\(-10^7 \leq x_i \leq 10^7\)。所有坐标按升序给出。

输出格式

输出共一行。爆虫的最小爆炸半径\(R\)。保留6位小数。

样例输入

5 2
-10.0 -6.0 10 11 15

样例输出

2.500000

样例说明

将第一只爆虫放在坐标\(-8\)处，第二只爆虫放在坐标\(12.5\)处。 这时，只要爆炸半径为\(2.5\)，就能消灭所有陆战队员。

数据规模

对于30%的数据，\( n \leq 50 \)。 对于所有的数据，\( n \leq 100,000 \)。

提示

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

#include <iostream>
#include <iomanip>

using namespace std;

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

限制

时间限制：1000ms，内存限制：50000kb。

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;
    }
    getAnswer(x, 0, 0, k);
    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;
}