Inversion

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 914 Accepted Submission(s): 380

Problem Description bobo has a sequence a ₁,a ₂,…,a _n. He is allowed to swap two adjacent numbers for no more than k times.

Find the minimum number of inversions after his swaps.

Note: The number of inversions is the number of pair (i,j) where 1≤i i>a _j.
Input The input consists of several tests. For each tests:

The first line contains 2 integers n,k (1≤n≤10 ⁵,0≤k≤10 ⁹). The second line contains n integers a ₁,a ₂,…,a _n (0≤a _i≤10 ⁹).
Output For each tests:

A single integer denotes the minimum number of inversions.
Sample Input

Sample Output

1
2

题意：n个数，最多有k次相邻位置的数的交换，问最小的逆序数为多少思路：保证每次交换逆序数都减小，可以参考冒泡排序的做法。最后只要计算原数列逆序数，然后减掉k即可。

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           using namespace std; const int maxn = 100000+10; int sum[maxn]; int n,k; int num[maxn],tn[maxn]; map
           
             mma; bool cmp(int a,int b){ return a > b; } int lowbit(int x){ return x&(-x); } void add(int x,int d){ while(x < maxn){ sum[x] += d; x += lowbit(x); } } int getS(int x){ int ret = 0; while(x > 0){ ret += sum[x]; x -= lowbit(x); } return ret; } int main(){ while(~scanf("%d%d",&n,&k)){ mma.clear(); memset(sum,0,sizeof sum); for(int i = 1; i <= n; i++){ scanf("%d",&num[i]); tn[i] = num[i]; } sort(tn+1,tn+n+1,cmp); int i = 1,cnt = 1; while(i <= n){ mma[tn[i]] = cnt; int j = i+1; while(j <= n && tn[i]==tn[j]){ j++; } cnt++; i = j; } long long ret = 0; for(int i = 1; i <= n; i++){ ret += getS(mma[num[i]]-1); add(mma[num[i]],1); } long long ans = ret-k; if(ans < 0) ans = 0; cout<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 1061 青蛙的约会(扩展GCD求模..	下一篇：The Perfect Stall

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: