因为只能交换相邻的两个数,其他数和这两个的数的相对位置没有影响,所以逆序数只会改变0,-1,+1,因为要求minimum,所以每次都让逆序数-1,因为操作no more than k times,当顺序的时候停止操作即可。
WA了好久还以为是模板错了,最后发现是因为把10W敲成了10000。。。以后直接写1e5+10好了==
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> #include<map> #include<time.h> using namespace std; //hdu 4911 const int maxn=100010; long long a[maxn]; int n; long long k; long long cnt; long long b[maxn]; long long c[maxn]; long long merge_sort (int l, int r) { if (l == r) return 0; int mid = (l + r) / 2; long long ret = merge_sort(l, mid) + merge_sort(mid+1, r); int mvl = l, mvr = mid+1, mv = l; while (mvl <= mid || mvr <= r) { if (mvr > r || (mvl <= mid && a[mvl] <= a[mvr])) { b[mv++] = a[mvl++]; } else { ret += mid - mvl + 1; b[mv++] = a[mvr++]; } } for (int i = l; i <= r; i++) a[i] = b[i]; return ret; } void mergesort(int l,int r) { int mid,i,j,tmp; if(r>l+1) { mid=(l+r)/2; mergesort(l,mid); mergesort(mid,r); tmp=l; for(i=l,j=mid;i<mid&&j<r;) { if(a[i]>a[j]) { c[tmp++]=a[j++]; cnt+=mid-i; } else c[tmp++]=a[i++]; } if(j<r) for(;j<r;++j) c[tmp++]=a[j]; else for(;i<mid;++i) c[tmp++]=a[i]; for(i=1;i<r;++i) a[i]=c[i]; } } int main() { freopen("input.txt","r",stdin); // freopen("data.txt","r",stdin); // freopen("out1.txt","w",stdout); while(scanf("%d %I64d",&n,&k)!=EOF) { memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cnt=0; for(int i=0;i<n;i++) { scanf("%I64d",&a[i]); } // cnt=merge_sort(1,n); cnt=merge_sort(0,n-1); long long ans=max(0LL,cnt-k); printf("%I64d\n",ans); } return 0; }