程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdoj 4911 Inversion 樹狀數組+離散化

hdoj 4911 Inversion 樹狀數組+離散化

編輯:C++入門知識

hdoj 4911 Inversion 樹狀數組+離散化


題意:給你n個可以重復的無序數列,問經過k次相鄰交換後最少還有多少對逆序數

求逆序對可以用樹狀數組來做,對於重復的元素,可能在sort的時候交換編號

求和的時候要注意去重,還有一種方法就是穩定排序stable_sort

 

#include
#include
#include
using namespace std;
#define ll __int64
#define N 100000+10
struct ln{
        int id,va;
}in[N];
int a[N],c[N];
int n;
int cmp(ln x,ln y)
{
        return x.va=1;i-=lowbit(i))
                temp+=c[i];
        return temp;
}
int main()
{
        int k;
        while(scanf("%d%d",&n,&k)!=EOF)
        {
                for(int i=1;i<=n;i++)
                {
                        scanf("%d",&in[i].va);
                        in[i].id=i;
                }
                memset(c,0,sizeof(c));
                sort(in+1,in+n+1,cmp);
                a[in[1].id]=1;
                for(int i=2;i<=n;i++)
                {
                        if(in[i].va!=in[i-1].va)
                        a[in[i].id]=i;
                        else
                        a[in[i].id]=a[in[i-1].id];

                }
                ll ans=0;
                for(int i=1;i<=n;i++)
                {
                   updata(a[i],1);
                   printf("%d %d\n",getSum(a[i]),getSum(a[i]-1));
                   int temp=i-getSum(a[i]-1);
                   temp=temp-(getSum(a[i])-getSum(a[i]-1));
                   ans+=temp;
                }
                if(ans-k<0) printf("0\n");
                else
                printf("%I64d\n",ans-k);

        }
        return 0;
}
#include
#include
#include
using namespace std;
#define ll __int64
#define N 100000+10
struct ln{
        int id,va;
}in[N];
int a[N],c[N];
int n;
int cmp(ln x,ln y)
{
        return x.va=1;i-=lowbit(i))
                temp+=c[i];
        return temp;
}
int main()
{
        int k;
        while(scanf("%d%d",&n,&k)!=EOF)
        {
                for(int i=1;i<=n;i++)
                {
                        scanf("%d",&in[i].va);
                        in[i].id=i;
                }
                memset(c,0,sizeof(c));
                stable_sort(in+1,in+n+1,cmp);
                for(int i=1;i<=n;i++)
                        a[in[i].id]=i;
                ll ans=0;
                for(int i=1;i<=n;i++)
                {
                   updata(a[i],1);

                   int temp=i-getSum(a[i]);

                   ans+=temp;
                }
                if(ans-k<0) printf("0\n");
                else
                printf("%I64d\n",ans-k);

        }
        return 0;
}



 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved