ptaR7-6/zzuli2106 有去有回

题目

输入n个整数，第一趟按从左到右间隔k个数取数据，然后第二趟再从右到左间隔k-1个数取余下的数，如果数据没有取完，下一趟再间隔k-2个从左到右取数据，如此反复，直到所有的数据取完为止。注意：每趟第1个数是要取的，取走的数不再统计间隔数内。

输入

第一行输入两个整数n和k（0<n<=10000，0<=k<1000)；
第二行输入n个int范围内的正整数，用空格隔开。

输出

按取数的顺序输出n个整数，用空隔隔开。

样例输入

6 1
1 2 3 4 5 6

样例输出

1 3 5 6 4 2

提示

数据范围
对于60%的数据，0 ≤k≤ 1
对于80%的数据，0 ≤k ≤ 10
对于100%的数据，0≤ k ≤ 1000

思路

本题的思路分为两种：

1.基本思路

采用标记的方法从两端来回颠倒，这里不做详细解释。

2.采用stack容器进行来回颠倒

可以采用stack容器进行来回的压栈和出栈，从而达到我们想要的目的，和想要的结果，这个思路的代码笔者将会详细进行解释和分析，详细代码如下。

代码实现

1.基本思路

#include <stdio.h>//第一种思路，用c语言代码编写，不过多解释
int main() {
	int n, k, i, N, count, flag;
	int a[10005];
	scanf("%d %d", &n, &k);
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	count = 0;
	while (count < n) {
		flag = 1;
		for (i = 0; i < n; i++) {
			if ((N == k || flag == 1) && a[i] != -1) {
				printf("%d ", a[i]);
				a[i] = -1;
				count++;
				N = 0;
				flag++;
			}
			if (a[i] != -1)
				N++;
		}
		if (count >= n)
			break;
		if (k > 0)
			k--;
		N = 0;
		flag = 1;
		for (i = n - 1; i >= 0; i--) {
			if ((N == k || flag == 1) && a[i] != -1) {
				printf("%d ", a[i]);
				a[i] = -1;
				N = 0;
				count++;
				flag++;
			}
			if (a[i] != -1)
				N++;
		}
		if (k > 0)
			k--;
	}
}

2.stack容器

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k,i,t,m=0,j=0;
	cin>>n>>k;//输入n为数的个数
	vector<int>A(n);//原数组
	vector<int>ans(n);//结果集
	for(i=0;i<n;i++)
		cin>>A[i];//输入
	stack<int>a,b;//用于来回反转的容器
	for(i=n-1;i>=0;i--){
		a.push(A[i]);//反向压栈，这样正好栈顶是第一个
	}
	while(!a.empty()){//一直进行到两个数组都为空
		t=a.top(),a.pop();//将顶部的取出来，并且删除该元素
		m++;//进行计数
		if(m%(k+1)==1||k==0)ans[j++]=t;
        //如果计数器对(k+1)取余==1，那么刚好就是该数，如果间隔是0，那么就顺序输入即可
		else b.push(t);//如果不是间隔数，那么压入b容器中，这样刚好反转顺序
		if(a.empty()){//如果a为空，那么两容器交换
			swap(a,b);
			k--;//完成一轮间隔取值，k自减
			m=0;//计数器更新
		}	
	}
	for(i=0;i<n;i++){
		cout<<ans[i]<<' ';//输出结果集
	}
}

反思

本题为我们引入了stl中stack容器的使用，两个stack容器能够不断地为我们提供反转的机会，比计数器有更好的想法和较小的时间复杂度，通过该思想，我们可以融会贯通，像这种来回颠倒的题目，都可以使用stack容器来代替来回颠倒的标志器，至此，我们对压栈出栈有了全新的理解和认知，希望大家通过本篇能够认识和熟悉stack，了解stl容器的强大和美妙。