问题 H: 稿件整理
问题 H: 稿件整理
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
面对每天敲代码找Bug的日子，小Q实在受够了，他决定放弃现在的IT技术岗位，追随自己的内心，重拾儿时的文学梦。
于是，他应聘到《中国梦月报》当了一名编辑。
一天，小Q和他的小伙伴们在核对刊物初稿，但是一位编辑不小心把稿件弄乱了——编辑可能将正反面弄反了，也可能将前后张打乱了！
稿件每面有一个页码，页码1总为正面，总页数n总为偶数。现在，假设只能通过正反面的翻转与前后张的交换来整理稿件，并且正反面的翻转与前后张的交换都算作一次整理。
给出当前的页码顺序，请问最少经过几次整理，才能将稿件的页码恢复升序？
特别说明：在一次操作中，前后页交换时不可以同时翻转奇偶面。
输入格式
输入包含多组测试用例。
每组数据第一行输入总页数n(1<=n<=100000)，接下去的一行输入n个数(1~n)，表示当前的页码顺序。
每两组输入之间有一空行。
输出格式
每组输出占一行，输出一个整数，表示需要的最少整理次数。
输入样例 复制
4
3 4 2 1
2
1 2
输出样例 复制
2
0
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int cut;
int a[50005],b[50005];
void merge_sort(int *A,int x,int y,int *T)
{
if(y-x>1)
{
int m=x+(y-x)/2;
int p=x,q=m,i=x;
merge_sort(A, x, m, T);
merge_sort(A, m, y, T);
while(p<m||q<y)
{
if(q>=y||(p<m&&A[p]<=A[q]))
T[i++]=A[p++];
else
{
cut+=m-p;
T[i++]=A[q++];
}
}
for(i=x;i<y;i++)
A[i]=T[i];
}
}
int main()
{
int n;
int x,y;
while(cin>>n)
{
cut=0;
for(int i=0;i<n/2;i++)
{
scanf("%d%d",&x,&y);
if(x>y)
{
cut++;
swap(x, y);
}
a[i]=x;
}
merge_sort(a, 0, n/2, b);
printf("%d\n",cut);
}
return 0;
}
评论