Bessie的好牌（队列）- POJ 3629

Description

Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a deck with K (N ≤ K ≤ 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;

（每次发牌，都将P张牌依次放到底部）

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.

Input

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

Output

* 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.

Sample Input

3 9 2

Sample Output

3

7

8

题意解析：

有n个人玩k张牌，其中牌中有k/n张GOOD牌，Bessie想的到所有的GOOD牌，但她的朋友给出了一些限制

1、发牌要从Bessie上家开始（也就是说Bessie是第n个人发牌）

2、每次发牌后将接下来的p张牌放到牌的最下面

3、要求找出GOOD牌所放的位置，要从小到大排序

源码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <map>
using namespace std;
const int maxn = 1e5 + 100;
const int inf = 0x7ffffff;

//好牌数组
int good_cards[maxn];

int main(void)
{
    //n个人，k张牌
    int n, k, p;
    scanf("%d %d %d", &n, &k, &p);

    //打牌的队列
    queue<int>q;

    //将k张牌放入队列
    for (int i = 1; i <= k; i++)
        q.push(i);  

    int loop_count = 1, good_card_count = 0;

    while (!q.empty())
    {
        //轮到给自己发牌
        if (loop_count % n == 0)
        {
            //好牌
            good_cards[good_card_count++] = q.front();
            //找完了
            if (good_card_count == n / k)
                break; 
        }
        loop_count++;
        //发牌
        q.pop();
        //每次发牌后将接下来的p张牌放到牌的最下面
        for (int j = 0; j < p; j++)
        {
            //取出队列的头
            int tmp = q.front();
            //放到队列的末尾
            q.push(tmp);
            //将头出队列
            q.pop();
        }
    }

    //排序，从小到大
    sort(good_cards, good_cards + good_card_count);

    //输出好牌
    for (int i = 0; i < good_card_count; i++)
        printf("%d\n", good_cards[i]);

    return 0;
}

这个源码是采用C++的queue实现的，如上篇所说，可以考虑使用数组实现，性能会提升很多。

关于队列：

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的数组实现：

队列可以用数组Q[1…m]来存储，数组的上界m即是队列所容许的最大容量。在队列的运算中需设两个指针：

head，队头指针，指向实际队头元素；

tail，队尾指针，指向实际队尾元素的下一个位置。

一般情况下，两个指针的初值设为0，这时队列为空，没有元素。数组定义Q[1…10]。Q(i) i=3,4,5,6,7,8。头指针head=2，尾指针tail=8。队列中拥有的元素个数为:L=tail-head。现要让排头的元素出队，则需将头指针加1。即head = head+1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q(9)入队。