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

___Mitsui_Hisashi___ · 2026-07-21 16:46:47 · 题解

Description

给定序列 c，任意排列 c 使得 \forall i\in[1,n],c_i \le i 并最大化 \min\limits_{i=1}^n \frac{c_i}{i}。

Analysis

先给结论：将 c 升序排列后能够最大化 \min\limits_{i=1}^n \frac{c_i}{i}。

证明：

对于当前的两个位置 i,j，由于已经排过序，我们不妨设 i<j，则 c_i<c_j，比例为 \frac{c_i}{i},\frac{c_j}{j}。若交换 c_i,c_j，则新比为 \frac{c_i}{j},\frac{c_j}{i}。不难发现 \frac{c_j}{i} > \frac{c_i}{i},\frac{c_i}{j}<\frac{c_j}{j}，因此交换后最小比值变小了。故排序后为最优解。

无解也很好判断，若 \exist i\in[1,n],c_i>i，则无解输出 impossible 即可。

时间复杂度 \mathcal O(n\log n)，主要在排序上。

Code

#include"bits/stdc++.h"
using namespace std;
const int N = 2e5 + 5;
int n, c[N];
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    sort(c + 1, c + 1 + n);
    for (int i = 1; i <= n; i++) 
        if (c[i] > i) {
            cout << "impossible";
            return 0;
        }
    double ans = 1;
    for (int i = 1; i <= n; i++)
        ans = min(ans, (double)c[i] / i);
    cout << ans;
    return 0;
}