首页 > 试题广场 >

怪异的洗牌

[编程题]怪异的洗牌

热度指数：3998 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

对于一副扑克牌，我们有多种不同的洗牌方式。一种方法是从中间某个位置分成两半，然后相交换，我们称之为移位（shift）。比如原来的次序是123456，从第4个位置交换，结果就是561234。这个方式其实就是数组的循环移位，为了多次进行这个操作，必须使用一种尽可能快的方法来编程实现。在本题目中，还引入另外一种洗牌方式，就是把前一半（如果总数是奇数，就是(n-1)/2）牌翻转过来，这种操作称之为翻转（flip）。在前面shift操作的结果上进行flip，结果就是165234。当然，如果是实际的扑克牌，直接翻转会造成正反面混在一起的，我们就不管那么多了。给定n张牌，初始次序为从1到n，经过若干次的shift和flip操作后，结果会是什么样？

输入描述:

输入包括多组测试数据，每组数据的第一行包括两个数 n和k。n表示牌的数目，1<n<1000，k表示下面要进行的操作数量。随后的k行，每行一个整数x，1<=x<=n，表示从第几个位置开始移位。在每一次shift操作后都接一个flip操作。

输出描述:

对于输入的每组数据，计算经过给定的k次shift和flip操作后，各个位置的数值。并按次序在一行上输出所有牌张的值，每个数值（不包括最后一个）后面有一个空格。

示例1

输入

6 1
4
0 0

输出

1 6 5 2 3 4

算法知识视频讲解

Java

牛客332198386号

好粗笨的方法..居然也过了。求java大神给更好的方案

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n=sc.nextInt();
			int k=sc.nextInt();
			if(n==0)break;
			List<Integer>list=new ArrayList<>();
			for(int i=1;i<=n;i++)
				list.add(i);
			while(k-->0) {
				int x=sc.nextInt();
				list=reverse(list,x);
				list=filp(list);
			}
			System.out.print(list.get(0));
			for(int i=1;i<n;i++)
				System.out.print(" "+list.get(i));
			System.out.println();
		}
	}

	private static List<Integer> filp(List<Integer> list) {
		List<Integer>after=new ArrayList<>();
		int len;
		if(list.size()%2==0)
			len=list.size()/2;
		else 
			len=(list.size()-1)/2;
		for(int i=0;i<len;i++) 
			after.add(list.get(i));
		Collections.reverse(after);
		for(int i=len;i<list.size();i++)
			after.add(list.get(i));
		return after;
	}

	private static List<Integer> reverse(List<Integer> list, int x) {
		List<Integer>after=new ArrayList<>();
		for(int i=x;i<list.size();i++)
			after.add(list.get(i));
		for(int i=0;i<x;i++)
			after.add(list.get(i));
		return after;
	}	
}

发表于 2020-04-10 15:39:52 回复(0)