Vijos P1988 – 自行车比赛 [贪心]

Link

https://vijos.org/p/1988

Problem

小雪非常关注自行车比赛,尤其是环滨湖自行车赛。一年一度的环滨湖自行车赛,需要选手们连续比赛数日,最终按照累计得分决出冠军。今年一共有N位参赛选手。每一天的比赛总会决出当日的排名,第一名的选手会获得N点得分,第二名会获得N-1点得分,第三名会获得N-2点得分,依次类推,最后一名会获得1点得分。保证没有选手会排名相同。

在之前的数日较量中,N位选手已经分别累计了一些分数。现在即将开始的是最后一天的比赛。小雪希望知道有多少位选手还有可能获得最终的冠军,也就是说还有多少选手有可能通过最后一天的比赛获得累计总分第一名。

Mean

有N个人进行比赛,之前已经进行了几轮比赛,每个人都有一定的分数。现在进行最后一轮比赛,每个人会分别获得1~N不同的分数。现在问有几个人会获得最高分赢得冠军。

Analysis

遍历N个人判断能否获得最高分。让当前这个人获得最高分(N分),其他人获得1~N-1分,原先分越高获得的分越低。然后只需要拿出原先有可能得到最高分的最多两个人跟这个人比较即可。

代码处理起来可以有很多技巧很短,为了可读性没有继续缩减,详见代码。

Code

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

const int maxn = 310000;

struct Node {
    int id, val, sum;
};
int N;
Node v[maxn];

bool judge(const Node &x) {
    int cur = x.val + N;
    for(int i = 0; i < 2; ++i) {
        if(v[i].id == x.id) continue;
        if(v[i].sum - (v[i].val < x.val) > cur)
            return false;
    }
    return true;
}

int main() {
    scanf("%d", &N);
    for(int i = 0; i < N; ++i) {
        scanf("%d", &v[i].val);
        v[i].id = i;
    }
    sort(v, v + N, [](const Node &a, const Node &b) { return a.val < b.val; });
    for(int i = 0; i < N; ++i)
        v[i].sum = v[i].val + N - i;
    nth_element(v, v + 2, v + N, [](const Node &a, const Node &b) { return a.sum > b.sum; });
    int ans = 0;
    for(int i = 0; i < N; ++i)
        if(judge(v[i])) ++ans;
    printf("%d\n", ans);
    return 0;
}

欢迎留言