Contest:
链接:https://ac.nowcoder.com/acm/problem/13947
来源:牛客网
n支队伍一共参加了三场比赛。
一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。
求有多少组(x,y),使得x自己觉得比y强,y自己也觉得比x强。
(x, y), (y, x)算一组。
输入描述:
第一行一个整数n,表示队伍数; 接下来n行,每行三个整数a[i], b[i], c[i],分别表示i在第一场、第二场和第三场比赛中的名次;n 最大不超过200000
输出描述:
输出一个整数表示满足条件的(x,y)数;64bit请用lld
题解:
题目应该是有个没有显式声明的条件:一场比赛种不存在两支队伍排名相同。
如果加上这个条件,也能做,处理一下这种情况即可。
第一点:考虑符合要求的队伍 和 三场比赛的排名。
显然只有两种情况: 出现两次, 出现一次;或者 出现两次, 出现一次;
那么我们从中任取两场比赛,对满足 和 各出现一次的做统计,结果数即为 。那么最终答案就是 。
因为同一对满足条件的 ,两种情况都是重复统计一次。
第二点:考虑两场比赛,如何统计 和 各出现一次。
记第一场比赛排名为 ,第二场比赛排名为 。
我们先按 排序。
那么即求 。即 数组的逆序对数。
常见求逆序对的方法有归并排序,或树状数组。
代码实现用树状数组。
树状数组维护区间。
区间中每个点 ,对应值为 的个数。
对于 ,区间 之和,即为 的值的个数。
顺序遍历 ,区间 之和计入答案,再更新树状数组,将 对应的值加一。
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn=2e5+10;
const LL mod=1e9+7;
const double pi=acos(-1.0);
inline LL read()
{
LL X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
LL n;
LL c[maxn];
LL a[maxn][3];
pair<LL,LL> p[maxn];
void add(LL x,LL d)
{
while(x<=n){
c[x]+=d;
x+=(x&(-x));
}
}
LL query(LL x)
{
LL ans=0;
while(x>0){
ans+=c[x];
x-=(x&(-x));
}
return ans;
}
int main()
{
scanf("%lld",&n);
for(LL i=1;i<=n;i++){
scanf("%lld%lld%lld",&a[i][0],&a[i][1],&a[i][2]);
}
LL res=0;
for(LL i=0;i<3;i++){
for(LL j=i+1;j<3;j++){
for(LL k=1;k<=n;k++){
p[k].first=a[k][i];p[k].second=a[k][j];
}
sort(p+1,p+1+n);
memset(c,0,sizeof(c));
for(LL k=1;k<=n;k++){
res+=(query(n)-query(p[k].second));
add(p[k].second,1);
}
}
}
printf("%lld\n",res/2);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)