最少的交换
题目描述
现在给你一个由 n 个互不相同的整数组成的序列, 现在要求你任意交换相邻的两个数字, 使序列成为升序序列, 请问最少的交换次数是多少?
输入
输入包含多组测试数据. 每组输入第一行是一个正整数 n(n<500000), 表示序列的长度, 当 n=0 时.
接下来的 n 行, 每行一个整数 a[i](0<=a[i]<=999999999), 表示序列中第 i 个元素.
输出
对于每组输入, 输出使得所给序列升序的最少交换次数.
样例输入
- 5
- 9
- 1
- 0
- 5
- 4
- 3
- 1
- 2
- 3
- 0
样例输出
6 0
- #include<iostream>
- using namespace std;
- int x[500050],b[500050];// 归并排序过程中累加所有逆序数
- long long num;// 注意交换次数类型
- void Merge(int data[], int low, int mid, int high)
- {
- int i = low, j = mid + 1, k = low;
- while (i <= mid && j <= high)
- {
- if (data[i] <= data[j])
- b[k++] = data[i++];
- else
- {
- num += j - k;
- b[k++] = data[j++];
- }
- }
- while (i <= mid)
- b[k++] = data[i++];
- while (j <= high)
- b[k++] = data[j++];
- for (i = low; i <= high; i++, k++)
- data[i] = b[i];
- }
- void MergeSort(int data[], int low, int high)
- {
- if (low<high)
- {
- int mid = (low + high) / 2;
- MergeSort(data, low, mid);
- MergeSort(data, mid + 1, high);
- Merge(data, low, mid, high);
- }
- }
- int main()
- {
- int n;
- while (cin>> n&&n)
- {
- for (int i = 0; i <n; i++)
- {
- cin>> x[i];
- }
- num = 0;
- MergeSort(x, 0, n - 1);
- cout <<num << endl;
- }
- return 0;
- }
- #include<iostream>
- using namespace std;
- int a[500010],b[500010];
- long long int count;
- void Merge(int start,int mid,int end)
- {
- int i=start,j=mid+1,tip=start;
- while(i<=mid&&j<=end)
- {
- if(a[i]<=a[j]) b[tip++]=a[i++];
- else
- count+=(j-tip),b[tip++]=a[j++];
- }
- while(i<=mid) b[tip++]=a[i++];
- while(j<=end) b[tip++]=a[j++];
- for(int i=start;i<=end;i++)
- a[i]=b[i];
- }
- void MergeSort(int start,int end)
- {
- if(start<end)
- {
- int mid=(start+end)/2;
- MergeSort(start,mid);
- MergeSort(mid+1,end);
- Merge(start,mid,end);
- }
- }
- int main()
- {
- int n;
- while(cin>>n&&n)
- {
- for(int i=1;i<=n;i++)
- cin>>a[i];
- count=0;
- MergeSort(1,n);
- cout<<count<<endl;
- }
- return 0;
- }
- View Code
最少的交换
来源: http://www.bubuko.com/infodetail-3108108.html