hdu4911逆序对+mergesort

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned int ui;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 #define pf printf
 7 #define mem(a,b) memset(a,b,sizeof(a))
 8 #define prime1 1e9+7
 9 #define prime2 1e9+9
10 #define pi 3.14159265
11 #define lson l,mid,rt<<1
12 #define rson mid+1,r,rt<<1|1
13 #define scand(x) scanf("%llf",&x) 
14 #define f(i,a,b) for(int i=a;i<=b;i++)
15 #define scan(a) scanf("%d",&a)
16 #define mp(a,b) make_pair((a),(b))
17 #define P pair<int,int>
18 #define dbg(args) cout<<#args<<":"<<args<<endl;
19 #define inf 0x7ffffff
20 inline int read(){
21     int ans=0,w=1;
22     char ch=getchar();
23     while(!isdigit(ch)){if(ch==‘-‘)w=-1;ch=getchar();}
24     while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-‘0‘,ch=getchar();
25     return ans*w;
26 }
27 int n,m,t;
28 const int maxn=1e5+10;
29 int a[maxn],b[maxn];
30 ll res=0;
31 void mergesort(int l,int r)
32 {
33     if(l==r)return;
34     int mid=l+r>>1;
35     mergesort(l,mid);
36     mergesort(mid+1,r);
37     int i=l,j=mid+1,cnt=0;
38     while(i<=mid&&j<=r)
39     {
40         if(a[i]>a[j])res+=mid-i+1,b[cnt++]=a[j++];
41         else b[cnt++]=a[i++];
42     }
43     while(i<=mid)b[cnt++]=a[i++];
44     while(j<=r)b[cnt++]=a[j++];
45     f(i,0,cnt-1)a[l+i]=b[i];//每次将指定长度的b数组复制回原数组 
46  } 
47 int main()
48 {
49     //freopen("input.txt","r",stdin);
50     //freopen("output.txt","w",stdout);
51     std::ios::sync_with_stdio(false);
52     while(~scanf("%d%d",&n,&m))
53     {
54         f(i,0,n-1)a[i]=read();
55         res=0;
56         mergesort(0,n-1);
57         if(m>=res)pf("0\n");
58         else pf("%lld\n",res-m);//不能将所有相邻逆序对交换 
59     }
60 }