专栏首页ACM算法日常Bessie的好牌(队列)- POJ 3629

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)入队。

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • 学会 01 串

    给定一个 01 串 S,求出它的一个尽可能长的子串 S[i..j],满足存在一个位置 i<=x <j, S[i..x]中 0 比 1 多,而 S[x + 1.....

    ACM算法日常
  • 爱彼迎19年社招java面试题 求DAG图中每个点的祖先个数

    例如上图, 则H的祖先个数是3个(包括它自己哈),分别是和. 而N的祖先个数是4()。

    ACM算法日常
  • Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) C. Connect(bfs)

    题目链接:http://codeforces.com/contest/1130/problem/C

    Ch_Zaqdt
  • 十种排序算法总结(冒泡、插入、选择、希尔、归并、堆、快速,计数,桶,基数)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    s1mba
  • 十种排序算法总结(冒泡、插入、选择、希尔、归并、堆、快速,计数,桶,基数)

    首先声明一下,本文只对十种排序算法做简单总结,并参照一些资料给出自己的代码实现,并没有对某种算法理论讲解,更详细的 了解可以参考以下资料(本人参考): 1、《d...

    s1mba
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • hdu 3518 (后缀数组)

      题目描述:   找出一个字符串中至少重复出现两次的字串的个数(重复出现时不能重叠)。   code:      后缀数组处理,对于得到height 进行查找...

    Gxjun
  • 1365 浴火银河星际跳跃

    1365 浴火银河星际跳跃 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 小...

    attack
  • C++反汇编第五讲,认识多重继承,菱形继承的内存结构,以及反汇编中的表现形式.

          C++反汇编第五讲,认识多重继承,菱形继承的内存结构,以及反汇编中的表现形式. 目录:   1.多重继承在内存中的表现形式     多重继承在汇编中...

    IBinary

扫码关注云+社区

领取腾讯云代金券