《直接用sort,有那么简单吗?Rt我全WA》续帖

P1908 逆序对

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 学啊大家都是从不会到学会的啊


上一页 |