sdut oj3663顺序表应用4-2：元素位置互换之逆置算法(数据改进）

题目链接：点击打开链接

顺序表应用4-2：元素位置互换之逆置算法(数据改进）

Time Limit: 80MS Memory Limit: 600KB Submit Statistic

Problem Description

一个长度为len(1<=len<=1000000)的顺序表，数据元素的类型为整型，将该表分成两半，前一半有m个元素，后一半有len-m个元素（1<=m<=len)，设计一个时间复杂度为O(N)、空间复杂度为O(1)的算法，改变原来的顺序表，把顺序表中原来在前的m个元素放到表的后段，后len-m个元素放到表的前段。 注意：交换操作会有多次，每次交换都是在上次交换完成后的顺序表中进行。

Input

第一行输入整数len(1<=len<=1000000)，表示顺序表元素的总数；

第二行输入len个整数，作为表里依次存放的数据元素；

第三行输入整数t(1<=t<=30)，表示之后要完成t次交换，每次均是在上次交换完成后的顺序表基础上实现新的交换；

之后t行，每行输入一个整数m(1<=m<=len)，代表本次交换要以上次交换完成后的顺序表为基础，实现前m个元素与后len-m个元素的交换；

Output

输出一共t行，每行依次输出本次交换完成后顺序表里所有元素。

Example Input

10 1 2 3 4 5 6 7 8 9 -1 3 2 3 5

Example Output

3 4 5 6 7 8 9 -1 1 2 6 7 8 9 -1 1 2 3 4 5 1 2 3 4 5 6 7 8 9 -1

Hint

Author

代码实现：

#include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; const int Maxsize = 1000100; typedef int element; typedef struct SqList { element *elem; int length; int listsize; } Sq; int InitList(Sq *L) { L->elem = (element *)malloc(Maxsize *sizeof(element)); if(!L->elem) return -1; L->length = 0; L->listsize = Maxsize; return 0; } void Creat(Sq *L,int k) { for(int i = 0; i < k; i++) scanf("%d",&L->elem[i]); L->length = k; } void Remove(Sq *L,int n,int m) { int i = n,j = m-1; while(i < j) { int t = L->elem[i]; L->elem[i] = L->elem[j]; L->elem[j] = t; i++;j--; } } void Display(Sq *L) { for(int i = 0; i < L->length-1; i++) printf("%d ",L->elem[i]); printf("%d\n",L->elem[L->length-1]); } int main() { int n,m; while(~scanf("%d",&n)) { Sq L; InitList(&L); Creat(&L,n); scanf("%d",&m); for(int i = 0;i < m;i++) { int k; scanf("%d",&k); Remove(&L,0,k); Remove(&L,k,n); Remove(&L,0,n); Display(&L); } } return 0; }