- 题目描述:
-
对于一副扑克牌,我们有多种不同的洗牌方式。一种方法是从中间某个位置分成两半,然后相交换,我们称之为移位(shift)。比如原来的次序是123456,从第4个位置交换,结果就是561234。这个方式其实就是数组的循环移位,为了多次进行这个操作,必须使用一种尽可能快的方法来编程实现。在本题目中,还引入另外一种洗牌方式,就是把前一半(如果总数是奇数,就是(n-1)/2)牌翻转过来,这种操作称之为翻转(flip)。在前面shift操作的结果上进行flip,结果就是165234。当然,如果是实际的扑克牌,直接翻转会造成正反面混在一起的,我们就不管那么多了。
给定n张牌,初始次序为从1到n,经过若干次的shift和flip操作后,结果会是什么样?
- 输入:
-
输入包括多组测试数据,每组数据的第一行包括两个数 n和k。n表示牌的数目,1<n<1000,如果n为0表示输入结束,k表示下面要进行的操作数量。随后的k行,每行一个整数x,1<=x<=n,表示从第几个位置开始移位。在每一次shift操作后都接一个flip操作。
- 输出:
-
对于输入的每组数据,计算经过给定的k次shift和flip操作后,各个位置的数值。并按次序在一行上输出所有牌张的值,每个数值(包括最后一个)后面有一个空格。
- 样例输入:
-
6 1 4 0 0
- 样例输出:
-
1 6 5 2 3 4
shift操作可以分解为三次reverse操作,flip操作就是一次reverse操作,所以程序的关键就是reverse操作。
C++代码:
#include<iostream> using namespace std; const int N=1000; int arr[N]; void myReverse(int s,int e){ int mid=(e-s+1)/2; for(int i=s;i<s+mid;i++){ int t=arr[i]; arr[i]=arr[e+s-i]; arr[e+s-i]=t; } } void shift(int n,int s){ myReverse(1,s); myReverse(s+1,n); myReverse(1,n); } int main(){ int n,k,t; while(cin>>n>>k&&n){ for(int i=0;i<=n;i++) arr[i]=i; for(int i=0;i<k;i++){ cin>>t; shift(n,t); if(n&1) myReverse(1,(n-1)/2); else myReverse(1,n/2); } for(int i=1;i<=n;i++) cout<<arr[i]<<" "; cout<<endl; } return 0; }