caojiaming @ 2023-01-30 16:12:15
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed n;
signed a[(int)1e6];
int cnt;
map<signed,signed> m;
signed Max=-1,Min=1e10;
signed x;
int sum;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
Max=max(Max,x);
Min=min(Min,x);
m[x]++;
}
for(int i=Min;i<=Max;i++)
{
if(m[i]>0)
{
sum+=m[i]*cnt;
cnt+=m[i];
}
}
cout<<sum<<"\n";
return 0;
}
这种做法的思想是从装箱计数最小数枚举到最大数,每碰到不等于0的mi就sum(结果)+=mi*cnt,cnt+=mi
这样统计每个数有多少个比他小,再求和,保证能得到正确答案,注意要用map,否则全MLE
结果全TLE
为什么还不对?
by Cap1taL @ 2023-02-01 18:14:58
@caojiaming 学啊大家都是从不会到学会的啊