codeforces 730E (数学)

124 阅读 0 评论 82 点赞

我是靠谱客的博主动听帅哥，最近开发中收集的这篇文章主要介绍codeforces 730E (数学)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：点击这里

题意：给出一个封榜时的榜单，按照封榜时的分数排序，每个队伍在封榜后分数会改变，名次也会对应的变化t名。现在要求一个揭晓的顺序最大化 $sum t$ 。

对于两个队伍i,j，考虑揭晓他们的相对顺序。如果这两个队在揭晓前和揭晓后相对排名不同，那么说明无论先揭晓哪个队伍，最后对答案的贡献总是1（画个图很容易看出来）。如果两个队揭晓前后相对排名不变，就分两种情况考虑：
1. 无论先后揭晓顺序如何，都不会使得一个队伍越过另一个队伍，这样的情况下显然先后顺序无所谓，对答案的贡献都是0；
2. 假设先揭晓i以后i的排名变化能够越过j，然后再揭晓j以后j的排名又会重新越过i，那么揭晓的顺序就先i后j，对答案的贡献是2，同理的情况亦然。
按照上述的方法，必然能够得到一个拓扑网络，然后按照拓扑关系即可得到一个揭晓的先后序列（当然题目没有要求，只要确定最大值即可）。
现在来证明这样的做法得到的关系图没有环：
因为只有第二种情况的第二点才会给关系图增加一条边，所以环只会在这里产生。假设有三个队伍i,j,k构成一个环，那么i揭晓后越过j，j揭晓后又重新越过i，jk和ki同理。显然这种情况不存在，因为ijk的相对次序必然是确定的，揭晓后的名次改变方向也必须一致，那么（i改变后越过j），（j改变后越过k）与（k改变后越过i相矛盾），如图：
这里写图片描述
于是不存在环关系，证毕。

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

struct node {
    int num, id, add;
    bool operator < (const node &a) const {
        return num > a.num || (num == a.num && id < a.id);
    }
}a[maxn];
int pre[maxn];
int n;

int ok (int i, int j) {
    node x = a[i], y = a[j], xx = x, yy = y;
    xx.num = x.num+x.add, yy.num = y.num+y.add;
    if (x < y && yy < xx) return 1;
    if (y < x && xx < yy) return 1;
    if (x < y && y < xx && xx < yy) return 2;
    if (y < x && x < yy && yy < xx) return 2;
    if (x < y && yy < x && xx < yy) return 2;
    if (y < x && xx < y && yy < xx) return 2;
    return 0;
}

int main () {
    //freopen ("more.in", "r", stdin);
    int ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].num >> a[i].add;
        a[i].id = i;
    }
    sort (a+1, a+1+n);
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            ans += ok (i, j);
        }
    }
    cout << ans << endl;
    return 0;
}