题意
n 个人，每人都与
CCi
与
TFi
。对于每个人，输出他所可能战胜的最大人数：
第 i 人可能战胜 j 的条件为（满足任意一条即可）:
CCi>CCj
或者
TFi>TFj
。i 能战胜 k 且 k 能战胜 j。
解题思路
首先对于每个人按照 CC 的分数从大到小排序，记录每个人 CC 排序的排名。
后按照 TF 的分数从大到小排序。
考虑 n 个人的子问题，其中 k 个人始终能战胜剩余的 n-k 个人，而 n-k 个人无论 CC 或 TF 值均小于 k 人中的任意一个，则此时这 k 人对 n-k 无影响。
对于 TF 排名第 i 的人，若其 CC 排名 poscc 大于 i ，则至少存在 poscc - i 人能战胜第 i 人。同时，第 i 人能够战胜 n-i 人。则
maxposccj(j∈[i,maxposcci])
- i 个人均能够战胜第 i 人 。
代码
#include<bits/stdc++.h>
using namespace std;
const int N =
100000 +
10;
const int RATING =
1000000 +
10;
struct Node {
int cc, tf, idx, poscc, postf;
} p[N], cpy[N];
bool cmp_cc(Node a, Node b) {
return a.cc > b.cc;
}
bool cmp_tf(Node a, Node b) {
return a.tf > b.tf;
}
int n, ans[N];
int main()
{
freopen(
"codecoder.in",
"r", stdin);
freopen(
"codecoder.out",
"w", stdout);
scanf(
"%d", &n);
for(
int i=
1;i<=n;i++)
{
scanf(
"%d %d",&p[i].cc, &p[i].tf);
p[i].idx = i;
}
sort(p+
1, p+n+
1, cmp_cc);
for(
int i=
1;i<=n;i++) {
p[i].poscc = i;
}
sort(p+
1, p+n+
1, cmp_tf);
for(
int i=
1;i<=n;i++)
{
int rgt = p[i].poscc;
for(
int j=i;j<=rgt;j++)
{
rgt = max(rgt, p[j].poscc);
ans[ p[j].idx ] = n-i;
}
i = rgt;
}
for(
int i=
1;i<=n;i++)
printf(
"%d\n", ans[i]);
}
