《直接用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 TankYu @ 2023-01-30 16:16:19

《min = 1e10》

by 喵仔牛奶 @ 2023-01-30 16:16:52

@caojiaming 你仔细看题目，你这个这么保证下标逆序

by caojiaming @ 2023-01-30 16:17:34

O(n)的时间复杂度(相当于箱排序)

应该可以过,为什么还过不了?

by caojiaming @ 2023-01-30 16:19:15

那就把输出改成cout<<n*n-sum

by caojiaming @ 2023-01-30 16:21:26

改一下

#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=Max;i>=Min;i--)
    {
        if(m[i]>0)
        {
            sum+=m[i]*cnt;
            cnt+=m[i];
        }
    }
    cout<<sum<<"\n";
    return 0;
}

by xiaoqian02 @ 2023-01-30 16:21:54

首先，如果卡，能卡到 10^9。

而且据说 map 不是 O(1) 的，好像是 O(log\;n)。

所以你可以试试这组数据：

4
114514 1919810 1 1000000000

by xiaoqian02 @ 2023-01-30 16:24:11

然后下标肯定也要寄掉，先 1 后 2 不算逆序对，即使时间过了也应该全 WA

by xiaoqian02 @ 2023-01-30 16:24:50

@caojiaming 还是好好写归并或者树状数组吧

by caojiaming @ 2023-01-30 16:27:58

那怎么搞我一样都不会? 怎么办怎么办?

while(1) cout<<"怎么办";

by 小明小红 @ 2023-01-30 16:32:01

不如用树状数组

| 下一页