首页技术正文

hdu 4911 Inversion and poj2299 [树状数组+离散化]

攻城狮世霖技术 2022年11月18日

0 收藏 613 点赞 3,009 浏览 1194 个字

题目

题意：给你一串数字，然后给你最多进行k次交换（只能交换相邻的）问交换后的最小逆序对个数是多少。

给你一个序列，每次只能交换相邻的位置，把他交换成一个递增序列所需要的最少步数等于整个序列的逆序对数。

对于这个题目，我们只要求出个逆序对个数，然后输出逆序数 – k就行了，如果是负数输出0。

之前做的这道题也是和逆序对有关，但是通过这道的代码改编一下，总是Runtime Error (ACCESS_VIOLATION)，原因在于这里

The first line contains 2 integers n,k (1≤n≤10^5,0≤k≤10^9). The second line contains n integers a1,a2,…,an (0≤ai≤10^9).

数据范围10^9，所需空间太大，需要离散化。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Max = 1e5+10;
int n;
LL c[Max];
LL Lowbit(int x)
{
    return x&(-x);
}
void update(int i,int x)
{
    while(i<=n){
        c[i]+=x;
        i+=Lowbit(i);
    }
}
LL getsum(int i)
{
    LL sum = 0;
    while(i>0)
    {
        sum+=c[i];
        i-= Lowbit(i);
    }
    return sum;
}
int main()
{
    int k;
    int a[Max],tmp[Max];
    while(cin>>n>>k)
    {
        for(int i=1;i<=n;i++){
            cin>>a[i];
            tmp[i]=a[i];
        }
        //离散化
        sort(tmp+1,tmp+1+n);
        int tol = unique(tmp+1,tmp+n+1)-tmp-1;
        for(int i=1;i<=n;i++)
            a[i]=lower_bound(tmp+1,tmp+tol+1,a[i])-tmp;        LL sum = 0;
        /*下面几行代码也可以写成这样
        for(int i=1;i<=n;i++)
        {
            update(a[i],1);
            sum+=i-getsum(a[i]);
        }
        */
        for(int i=n;i>0;i--)
        {
            sum=sum+getsum(a[i]-1);
            //getsum()是对 [1,a[i] ]求和,而这里我要求的是比a[i]小的，不包括a[i],即a[i]-1
            update(a[i],1);
        }
        sum -= k;
        if(sum<0) sum = 0;
        cout<<sum<<endl;        memset(c,0,sizeof(c));
        memset(a,0,sizeof(a));
        memset(tmp,0,sizeof(tmp));
    }
    return 0;
}