package 蓝桥杯;
import java.util.Scanner;
//算法由归并排序改进，加入MergeSortAndCount
//如果逆序数大于0，那么必定存在1<=i<n使得i和i+1交换后逆序数减1
//假设原逆序数为cnt，这样的话，我们就可以得到答案是max（cnt-k,0）
public class VO分治_inversion {
static long n;
static long count=0;
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
while(reader.hasNext()) {
count=0;
int n=reader.nextInt();
long k=reader.nextLong();
long[] a=new long[n];
long[] b=new long[n];
for(int i=0;i<n;i++) {
a[i]=reader.nextLong();
}
MergeSort(a,0,n-1,b);
if(count-k>0)
System.out.println(count-k);
else System.out.println(count);
}
}
static void swap(long[] a,int i,int j) {
long t=a[i];
a[i]=a[j];
a[j]=t;
}
static void MergeSort(long[] a,int s,int e,long[] b) {
if(s<e) {
int m=s+(e-s)/2;
MergeSort(a, s, m, b);
MergeSort(a, m+1, e, b);
MergeSortAndCount(a, s,m, e, b);//在O(n)的时间内实现有多少逆序数由左半边和右半边各取一个数构成。
}
}
static void MergeSortAndCount(long[] a,int s,int m,int e,long[] b) {
int pb=0;
int p1=s,p2=m+1;
while(p1<=m&&p2<=e) {
if(a[p1]>a[p2]) {
count+=e-p2+1;//！！！假如在原来的数组里面就存在逆序列才累加
b[pb++]=a[p1++];
}
else b[pb++]=a[p2++];
}
while(p1<=m)
b[pb++]=a[p1++];
while(p2<=e)
b[pb++]=a[p2++];
for(int i=0;i<e-s+1;i++)
a[s+i]=b[i];
//最后再累计的结果是错误的！！！
}
}
package 蓝桥杯;
import java.util.Arrays;
import java.util.Scanner;
public class VO分治_输出前m大的数 {
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
while(reader.hasNext()) {
int n=reader.nextInt();
int m=reader.nextInt();
int[] b=new int[n];//存放输入的数组
int[] a=new int[n*(n-1)/2];//存放两两之和
for(int i=0;i<n;i++) {
b[i]=reader.nextInt();
}
int h=0;//标记a数组的下标；
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
a[h++]=b[i]+b[j];
arrangeRight(a, 0, h-1, m);
int fromIndex=h-m;
int toIndex=h;
Arrays.sort(a, fromIndex, toIndex);
int count=0;//记录倒叙输出数组a的个数
for(int i=h-1;count<m&&i>=0;i--,count++) {
if(count==m-1)
System.out.print(a[i]);
else
System.out.print(a[i]+" ");
}
//System.out.print(a[h-m+1]);
System.out.println();//输出一行，要单独添加一个换行符
}
}
static void arrangeRight(int[] a,int s,int e,int m) {
if(s>=e)
return ;
int k=a[s];
int i=s,j=e;
while(i!=j) {
while(i<j&&a[j]>=k)
j--;
swap(a,i,j);
while(i<j&&a[i]<=k)
i++;
swap(a,i, j);
}
int C=e-i+1;//经过一次快排之后数组右边的数量
if(C==m) return;//这个时候右边还是无序的。
else if(C>m) arrangeRight(a, i+1, e, m);//将i加1缩小范围
else if(C<m) arrangeRight(a, s, i-1, m-C);
}
static void swap(int[] a,int i,int j) {
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
package 蓝桥杯;
public class VO分治_MergeSort {
static int[] a= {3,3,4,6,2,6,3,2,23,10};
static int[] b=new int[10];
public static void main(String[] args) {
int size=a.length;
MergeSort(a,0,size-1,b);
for(int i=0;i<size;i++) {
System.out.print(a[i]+" ");
}
}
static void MergeSort(int[] a,int s,int e,int[] b) {
if(s<e) {
int m=s+(e-s)/2;
MergeSort(a, s, m, b);
MergeSort(a, m+1, e, b);
Merge(a, s,m, e, b);
}
}
static void Merge(int[] a,int s,int m,int e,int[] b) {
int pb=0;
int p1=s,p2=m+1;
while(p1<=m&&p2<=e) {
if(a[p1]<a[p2])
b[pb++]=a[p1++];
else b[pb++]=a[p2++];
}
while(p1<=m)
b[pb++]=a[p1++];
while(p2<=e)
b[pb++]=a[p2++];
for(int i=0;i<e-s+1;i++)
a[s+i]=b[i];
}
}
package 蓝桥杯;
public class VO分治_QuickSort {
static int[] a= {10,2,3,5,4,68,4,4,6,9};
public static void main(String[] args) {
int size=a.length;
QuickSort(a,0,size-1);
for(int i=0;i<size;i++) {
System.out.print(a[i]+" ");
}
}
static void QuickSort(int[] a,int s,int e) {
if(s>=e)
return ;
int k=a[s];
int i=s,j=e;
while(i!=j) {
while(i<j&&a[j]>=k)//大的就在后面不动
j--;
swap(i,j);
while(i<j&&a[i]<=k)
i++;
swap(i, j);
}
QuickSort(a, s, i-1);
QuickSort(a, i+1, e);
}
static void swap(int i,int j) {
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
package 蓝桥杯;
import java.util.Scanner;
//算法由归并排序改
阅读背景：
（Java）分治_inversion、分治_输出前m大的数、分治_MergeSort、分治_QuickSort
来源：互联网
分享到：
