首页 > 专题系列 > Java解POJ > POJ 3629 Card Stacking [解题报告] Java
2013
11-13

POJ 3629 Card Stacking [解题报告] Java

Card Stacking

问题描述 :

Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a deck with K (NK ≤ 100,000; K is a multiple of N) cards. The deck contains M = K/N "good" cards and K-M "bad" cards. Bessie is the dealer and, naturally, wants to deal herself all of the "good" cards. She loves winning.

Her friends suspect that she will cheat, though, so they devise a dealing system in an attempt to prevent Bessie from cheating. They tell her to deal as follows:

1. Start by dealing the card on the top of the deck to the cow to her right

2. Every time she deals a card, she must place the next P (1 ≤ P ≤ 10) cards on the bottom of the deck; and

3. Continue dealing in this manner to each player sequentially in a counterclockwise manner

Bessie, desperate to win, asks you to help her figure out where she should put the "good" cards so that she gets all of them. Notationally, the top card is card #1, next card is #2, and so on.

输入:

* Line 1: Three space-separated integers: N, K, and P

输出:

* Lines 1..M: Positions from top in ascending order in which Bessie should place "good" cards, such that when dealt, Bessie will obtain all good cards.

样例输入:

3 9 2

样例输出:

3
7
8

解题代码:

import java.util.Arrays;   
import java.util.Scanner;   
  
public class Main {   
    int queue[], head, tail;//记录队列,队列头和尾   
  
    void enque(int x) {   
        queue[tail] = x;   
        tail++;   
        if (tail == k)   
            tail = 0;   
    }   
    int deque() {   
        int ans = queue[head];   
        head++;   
        if (head == k)   
            head = 0;   
        return ans;   
    }   
  
    int n, m, k, p;   
    int res[];   
    Scanner scan = new Scanner(System.in);   
  
        //队列初始化   
    void init() {   
        n = scan.nextInt();   
        k = scan.nextInt();   
        p = scan.nextInt();   
        queue = new int[k];   
        m = k / n;   
        res = new int[m];   
        for (int i = 1; i <= k; i++)   
            enque(i);   
    }   
  
    void run() {   
        init();   
  
        //模拟发牌过程   
        for (int x = 0; x< m; x++)   
            for (int i = 1; i <= n; i++) {   
                if (i == n)   
                    res[x] = deque();   
                else  
                    deque();   
                for (int j = 0; j < p; j++)   
                    enque(deque());   
            }   
        Arrays.sort(res);   
        for (int i = 0; i < m; i++)   
            System.out.println(res[i]);   
    }   
  
    public static void main(String[] args)  {   
        new Main().run();   
    }   
}  

解法二:
import java.util.Scanner;   
import java.util.Queue;   
import java.util.LinkedList;   
import java.util.Arrays;   
public class Main    
{      
    public static void main(String[] args)   
    {   
        Scanner scan=new Scanner(System.in);   
        int n=scan.nextInt();   
        int k=scan.nextInt();   
        int p=scan.nextInt();   
           
        Queue< Integer> q=new LinkedList< Integer>();   
        //int b=q.peek();   
        //向队列添加元素   
        for(int i=0;i< k;i++)   
        {   
            q.offer(i+1);   
        }      
        int[] arr=new int[k/n];   
        int s=0;   
        for(int w=1;w<=k/n;w++,s++)   
        {   
            for(int i=1;i< n;i++)   
            {   
                q.poll();   
                for(int j=1;j<=p;j++)   
                {   
                   q.offer(q.peek());//offer(E e)将指定的元素插入此队列   
                   q.poll();   
                }   
            }   
            arr[s]=q.peek();   
               
            q.poll();   
            for(int j=1;j<=p;j++)   
            {   
                q.offer(q.peek());   
                q.poll();   
            }   
        }   
        Arrays.sort(arr);   
        for(int i=0;i< arr.length;i++)   
        {   
            System.out.println(arr[i]);   
        }   
    }   
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮