AtCoder Beginner Contest 159 D Banned K 统计相同数值的元素数量+排列组合

数值的元素数量+排列组合"/>

AtCoder Beginner Contest 159 D Banned K 统计相同数值的元素数量+排列组合

AtCoder Beginner Contest 159   比赛人数8276  快,比赛开始后3分钟看到所有题

AtCoder Beginner Contest 159 D Banned K  统计相同数值的元素数量+排列组合

总目录详见

在线测评地址

统计相同数值的元素数量+排列组合

AC代码如下

#include <cstdio>
#include <algorithm>
#define LL long long
#define maxn 200010
using namespace std;
int a[maxn],n,cnt[maxn],mx;//cnt[]统计相同数值的元素数量
LL ans,out;
int main(){int i;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++,mx=max(mx,a[i]);for(i=1;i<=mx;i++)if(cnt[i]>=2)ans+=(LL)cnt[i]*(cnt[i]-1)/2;//任选2个for(i=1;i<=n;i++){if(cnt[a[i]]>=2){out=ans-cnt[a[i]]*(cnt[a[i]]-1)/2;//先扣除out+=(cnt[a[i]]-1)*(cnt[a[i]]-1-1)/2;//再加回}else out=ans;printf("%lld\n",out);}return 0;
}