题意
有 \(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
标签:dots,学科,int,题解,智力,Delta,排名
From: https://www.cnblogs.com/zphh/p/18449015