题解:Incremental Induction

这题的难点在于

• 1.阅读理解
• 2.统计答案时的思路

1.题意

地址:https://vjudge.net/problem/Kattis-incrementalinduction
The Nordic Collegiate Pong Championship (NCPC) is an insanely competive tournament where every contestant plays exactly one game of Pong against every other contestant. The last game of the tournament just finished, so only one item now remains on the programme: the traditional diploma ceremony, where all this year’s participants get inducted into the NCPC Hall of Fame.
According to the ancient customs, contestants who have not been inducted into the Hall of Fame yet (the pathetic nobodies) must stay on the left side of the stage, whereas contestants who have been inducted (the awesome legends) must be on the right side of the stage. Then, when a contestant is receiving their diploma, they will symbolically walk from the left to the right side of the stage and thus become an awesome legend. Only one contestant is inducted into the Hall of Fame at a time, and every contestant starts on the left side initially.

The NCPC Head of Jury believes it reflects badly on her if too many of the awesome legends on the right have lost matches against pathetic nobodies on the left, but she quickly realizes that it might be impossible to avoid this at every point in time during the diploma ceremony. However, she certainly wants to keep such atrocities at a minimum. Specifically, she wants to find the smallest number k for which there exists an order of handing out diplomas to the contestants, such that at no point there were more than k games played where an awesome legend lost against a pathetic nobody.

大致意思是：有n（n<=5000）个人需要去领奖，已经领奖的人就会变成大师，没有领奖的人就是菜鸡。每两人之间都会有对应的强弱关系。每当有一个人要去领奖时，对于每一对菜鸡和大师（场上所有人组成的关系而不是当前领奖者和所有大师组成的关系），k为当前情况下菜鸡战胜大师的对数。要求你求出一个合适的领奖顺序，使得k最小。输出最小的k值。

输入输出阅读原题

2.解法

很显然，我们应该让实力更强的人先去领奖。

在这个原则下，很显然的我们需要$n^2$的时间统计当前所有的菜鸡打败大师的数量，总的时间复杂度就是$n^3$,显然会TLE。对于每一对强弱关系，比如i强于j，则i向j连一条边。对于每个点的出度排序（入度也可，不过后面就要反着了）。

对于一个状态，它的k值就是noobs集合到masters集合的边的总数
$$\sum_j^{j\in masters}{d[j]}-\frac {i \times (i-1)}2$$

因为每两个人之间都会有强弱关系，所以一这张图是一张完全图。所有所以两个集合之间的边数等于masters集合的出度数-master集合内部的所有边的数量，即为上式。
o(n)求解即可

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5e3+7;
int a[MAXN][MAXN],vis[MAXN];
struct node{
    int v,num;
}d[MAXN];
inline bool cmp(const node a,const node b){
    return a.v<b.v;
}
inline int Max(const int a,const int b){
    return a>b?a:b;
}
int main(){
    int n;
    scanf("%d",&n);getchar();
    for(int i=1;i<=n;i++){
        d[i].num=i;
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            a[i][j]=getchar()-'0';
            a[j][i]=a[i][j]^1;
            if(a[i][j])d[i].v++;
            else d[j].v++;
        }
        getchar();
    }
    sort(d+1,d+n+1,cmp);
    int ans=0,res=0;
    for(int i=1;i<=n;i++){
        //vis[d[i].num]=1;
        // for(int j=1;j<=n;j++){
        //     if(i == j) continue;
        //     if(a[d[i].num][d[j].num] && !vis[d[j].num])res++;
        //     else if(a[d[j].num][d[i].num] && vis[d[j].num])res--;   
        // }
        //另外n^2的方法是反着统计的，图上的更好理解
        res+=d[i].v;
        ans=Max(ans,res-(i*(i-1))/2); //有向完全图，所以右边内部的边数=(i*(i-1))/2
    }
    cout<<ans;
    return 0;
}