思维)"/>
Banned K(思维)
思路
先统计球上每个数字出现的次数。不考虑去掉k的情况下,算出取出两个球上数字相同的总数sum。在考虑去掉k球的情况,答案即为sum-vis[a[k]]*(vis[a[k]]-1)/2+(vis[a[k]]-1)*(vis[a[k]]-2)/2
solution
#include <stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxx = 2e5 + 10;
ll vis[maxx];
ll a[maxx];
int n;
int main()
{scanf("%d",&n);ll ma=-0x3f3f3f3f;ll sum=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);vis[a[i]]++;ma=max(ma,a[i]);}for(int i=1;i<=ma;i++){if(vis[i]>=2){sum+=vis[i]*(vis[i]-1)/2;}}for(int i=1;i<=n;i++){if(vis[a[i]]>=2) printf("%lld\n",sum-vis[a[i]]*(vis[a[i]]-1)/2+(vis[a[i]]-1)*(vis[a[i]]-2)/2);else printf("%lld\n",sum);}// system("pause");
}
更多推荐
Banned K(思维)
发布评论