截绳子

题目描述

有 $n$ 段绳子，长短不一。现在要从中截出 $k$ 段长度相同的绳子。当然，一段绳子可以截出来多段绳子。截出来的绳子最长是多少？

输入格式

第一行两个整数 $n$ 和 $k$ ($1 \le n, k \le 10^5$)
接下来 $n$ 行，每行有一个整数 $a_i$ ($1 \le a_i \le 10^7$)，代表每根绳子的长度

输出格式

一个数，代表最长长度。相对误差或绝对误差不超过 $10^{-6}$

测试样例

样例 1
输入:

4 11
802
743
457
539

输出:

200.5

方法一

#include <bits/stdc++.h>
using namespace std;

vector<int> a;
int n, k, t;
double eps = 1e-6, mid, ma, mi = 0;

bool check(const double& len) {
    int cnt = 0;
    for(auto&i:a){
        cnt += i / len;
        if(cnt>=k)
            return true;
    }
    return false;
}
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &t);
        a.emplace_back(t);
    }
    sort(a.begin(), a.end(), greater<int>());
    ma = a[0];
    while (ma - mi > eps) {
        mid = (ma + mi) / 2;
        if (check(mid)) {
            mi = mid;
        } else {
            ma = mid;
        }
    }
    printf("%.6f", ma);
    return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, t;

double ans;
vector<int> cnt(100005, 1);
double rope[100005];
struct sz {
    double len = 0;
    int index = 0;
    sz() {}
    sz(double tlen, int tindex) {
        len = tlen, index = tindex;
    }
    bool operator<(const sz& s) const {
        return len < s.len;
    }
};
priority_queue<sz> p;

int main() {
    freopen("a.in", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &t);
        rope[i] = t;
        p.emplace(t, i);
    }
    for (int i = 0; i < k; ++i) {
        sz big = p.top();
        p.pop();
        ans = big.len;
        cnt[big.index]++;
        p.emplace(rope[big.index] / cnt[big.index], big.index);
    }
    cout << ans;
    return 0;
}