问题 H: 稿件整理
C语言题库
共 1520字,需浏览 4分钟
·
2021-04-13 02:00
问题 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;
}
评论