问题 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;
}


浏览 10
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报