P9587 排名 的题解

· · 题解

题目大意

传送门

题目已经很简短了，不好概括。

大体思路

先讲一下 20 分的做法，从部分分做起可以更深的理解题意。

看题目中的特殊性质 B，既然 k=1 那么 f(i) 就必须为 1，而 g(i) 又必须大于 0，所以当前的数就必须和最大数平齐，所以对于每一个 i，答案就是 maxx-a_i，其中 maxx 为数列最大值。

代码如下：

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

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

int c,n,k,maxx = 0;
int a[500007];

int main(){
    c = read(), n = read(), k = read();
    for(int i = 1; i <= n; i++) a[i] = read(), maxx = max(maxx, a[i]);
    if(k == 1) {
        for(int i = 1; i <= n; i++)
            printf("%d\n", maxx - a[i]);
        return 0;
    }

    return 0;
}

得完这档部分分，相信大家对于 f(i) 和 g(i) 都有了更深的理解。

那么我们考虑 100 分做法。

我在做这题的时候有一种下意识，当我发现题目怎么暴力也暴力不出来的时候，就想到分情况讨论，找规律。

首先，我们得先给数组排个序。

于是有如下几种情况：

其中第二个式子可以直接用前缀和优化。

由于要排序，时间复杂度为 O(n \log n)。

代码如下：

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

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

int _,n,k,maxx=0;
struct node {
    int x, num;
} a[500007];
ll sum[500007], ans[500007];
inline bool cmp(node i, node j) { return i.x > j.x; }
int main(){
    _ = read(), n = read(), k = read();
    for(int i = 1; i <= n; i++) a[i].x = read(), a[i].num = i;
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i].x;
    for(int i = 1; i <= n; i++) {
        if(a[i].x == a[k].x) continue;
        if(a[i].x < a[k].x) ans[a[i].num] = a[k].x - a[i].x;
        else ans[a[i].num] = (k - i) * 1ll * a[i].x - (sum[k] - sum[i]);
    }
    for(int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}