题意分析

用完全有向图表示，每个顶点代表一个玩家 边$x \rightarrow y$表示玩家$x$击败玩家$y$

玩家$x$的得分$s_x$是被$x$击败的玩家数量 得分序列$S(T)=(s_1,s_2,...,s_n)$是所有玩家得分的非递减排序 玩家$x$是强王，当且仅当$x$击败了所有得分比$x$高的玩家 即：对于所有$s_y > s_x$，存在边$x \rightarrow y$ 在所有实现给定得分序列$S$的锦标赛中，拥有最多强王的锦标赛

问题要求

给定一个得分序列$S$，找出重型锦标赛中强王的最大可能数量。

解题思路

关键观察

必须满足$\sum_{i=1}^k s_i \geq \binom{k}{2}$，对所有$1 \leq k \leq n$ 当$k=n$时，$\sum_{i=1}^n s_i = \binom{n}{2}$ 对玩家$x$，检查是否击败了所有$s_y > s_x$的玩家 得分相同的玩家之间胜负不影响强王判定 需要合理安排同分玩家之间的胜负关系 高得分玩家应尽可能被多个低得分玩家击败

算法设计

将得分序列$S$排序（非递减） 统计每个得分的出现次数 从高得分到低得分处理： 最高得分玩家自动成为强王 对每个得分$s$，计算可以有多少玩家满足： 击败所有$>s$的玩家 不被同分或更低分玩家影响

贪心策略： 让尽可能多的玩家满足强王条件 同分玩家之间构造循环胜负（如A→B→C→A） 低分玩家必须击败所有高分玩家

复杂度分析

时间：$O(n^2)$，需要检查每个玩家对其他玩家的胜负关系 空间：$O(n)$，存储得分序列和统计信息

标程

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN = 1e3+5;
const int INF = 0x3f3f3f3f;
typedef long long LL;

struct lp{
    int to,nex,cap,flow;
}cw[MAXN*10];
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
int n,m;
int ar[MAXN],mp[MAXN][MAXN];
char tools[100000];

void init(){
    tol = 0;
    // 手动初始化 head 数组
    for (int i = 0; i < MAXN; ++i) {
        head[i] = -1;
    }
}

void add(int u,int v,int w,int rw = 0){
    cw[tol].to = v;
    cw[tol].cap = w;
    cw[tol].nex = head[u];
    cw[tol].flow = 0;
    head[u] = tol++;
    cw[tol].to = u;
    cw[tol].cap = rw;
    cw[tol].nex = head[v];
    cw[tol].flow = 0;
    head[v] = tol++;
}

int sap(int start,int end,int N){
    // 手动初始化 gap 数组
    for (int i = 0; i < MAXN; ++i) {
        gap[i] = 0;
    }
    // 手动初始化 dep 数组
    for (int i = 0; i < MAXN; ++i) {
        dep[i] = 0;
    }
    // 手动复制 head 数组到 cur 数组
    for (int i = 0; i < MAXN; ++i) {
        cur[i] = head[i];
    }
    int u = start;
    pre[u] = -1;
    gap[0] = N;
    int ans = 0;
    while(dep[start] < N){
        if(u == end){
            int Min = INF;
            for(int i = pre[u]; i != -1;i = pre[cw[i^1].to])
                if(Min > cw[i].cap - cw[i].flow)
                    Min = cw[i].cap - cw[i].flow;
            for(int i = pre[u];i != -1;i = pre[cw[i^1].to]){
                cw[i].flow += Min;
                cw[i^1].flow -= Min;
            }
            u = start;
            ans += Min;
            continue;
        }
        bool flag = false;
        int v;
        for(int i = cur[u];i != -1;i = cw[i].nex){
            v = cw[i].to;
            if(cw[i].cap - cw[i].flow && dep[v] + 1 == dep[u]){
                flag = true;
                cur[u] = pre[v] = i;
                break;
            }
        }
        if(flag){
            u = v;
            continue;
        }
        int Min = N;
        for(int i = head[u];i != -1;i = cw[i].nex)
            if(cw[i].cap - cw[i].flow && dep[cw[i].to] < Min){
                Min = dep[cw[i].to];
                cur[u] = i;
            }
        gap[dep[u]]--;
        if(!gap[dep[u]])return ans;
        dep[u] = Min+1;
        gap[dep[u]]++;
        if(u != start)u = cw[pre[u]^1].to;
    }
    return ans;
}

int build(int k){
    init();
    int vs=0,vt=m+1;
    for(int i=1;i<=n;++i){
        add(vs,i,ar[i]);
        for(int j=i+1;j<=n;++j){
            if(i>=n-k+1&&ar[i]<ar[j]){
                add(i,mp[i][j],1);
            }else{
                add(i,mp[i][j],1);
                add(j,mp[i][j],1);
            }
            add(mp[i][j],vt,1);
        }
    }
    return sap(vs,vt,vt+1);
}

void cut(char *s){
    int len = strlen(s);  
    int t = 0;
    for(int i = 0; i < len; i++){
        if(s[i] >= '0' && s[i] <= '9'){
            t = t * 10 + s[i] - '0';
            if(i == len - 1 || s[i + 1] == ' '){
                ar[++n] = t;  
                t = 0;  
            }  
        }  
    }  
}  

int main(){
    int T;scanf("%d",&T);
    getchar();
    while(T--){n=0;
        // 手动初始化 tools 数组
        for (int i = 0; i < 100000; ++i) {
            tools[i] = 0;
        }
        gets(tools);
        cut(tools);
        m=n;
        for(int i=1;i<n;++i){
            for(int j=i+1;j<=n;++j){
                mp[i][j]=mp[j][i]=++m;
            }
        }
        for(int i=n;i>=1;--i){
            if(build(i)==n*(n-1)/2){
                printf("%d\n",i );
                break;
            }
        }
    }
    return 0;
}