题解：P16992 [NWERC 2018] 充气 / Inflation

_jry_qwq_ · 2026-07-21 21:20:25 · 题解

P16992 [NWERC 2018] 充气 / Inflation 题解

思路

气罐排序后从小到大配给容量 1 到 n 的气球。

证明：最小的气罐 c_1 必须配给最小的气球 1。如果 c_1 给了容量 j>1，而容量 1 的气球用了 c_k \ge c_1，交换两者后：

• 容量 1 的比例从 c_k 降到 c_1。
• 容量 j 的比例从 \frac{c_1}{j} 升到 \frac{c_k}{j}。

交换后最小比例不会变大，所以这样配最优。归纳下去即可。

配对后若 c_i > i 则无解，否则答案就是 \min(c_i / i)。 ::::success[code]

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

#define int long long
#define endl '\n'
const int N = 2e5 + 10;

int n;
int c[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> c[i];
    }

    sort(c + 1, c + 1 + n);

    double mmin = 1;
    for(int i = 1; i <= n; i ++){
        if(c[i] > i){
            cout << "impossible";
            return 0;
        }

        mmin = min(mmin, (double)c[i] / i);
    }

    cout << fixed << setprecision(6) << mmin;

    return 0;
}