鲁的智力 题解

题意

有 \(n\) 个人，\(m\) 个学科，你第 \(i\) 门学科排在第 \(a_i\) 名，且每个人在每个学科得到的分数是一个 \(0\) 到 \(1\) 之间的一个实数，求你总分排名的最大、小值。

题解

先考虑排名最高的情况。

我们可以每一科都这样构造：

\[b_1 = 1 \]

\[b_2 = 1 – \Delta x \]

\[b_3 = 1 – 2\Delta x \]

\[\dots \]

\[b_k = 1 – (k – 1)\Delta x \]

\[b_{k + 1} = 0 + (n – k)\Delta x \]

\[b_{k + 2} = 0 + (n – k – 1)\Delta x \]

\[\dots \]

\[b_n = 0 \]

其中 \(k\) 为你的排名、\(b_i\) 为第 \(i\) 名的分数、\(\Delta x\) 是一个极小值。

这样可以使得有任意一科在你下面的都会被你超越，此时你排名最高。

最低同理。

namespace zqh {
int n, m;

void init() {
    cin >> n >> m;
    int x = 0, y = 0;
    for (int i = 1; i <= n; i++) {
        int s;
        cin >> s;
        x += s - 1;
        y += m - s;
    }
    cout << max(1LL, m - y) << "\n" << min(m, x + 1);
}

void solve() {}

void main() {
    init();
    solve();
}
}  // namespace zqh