[數據結構][隊列]USACO Dec07 Bronze Card Stacking 洗牌作弊 cheat

題目描述

譯 by CmYkRgB123

貝茜正在和她的N-1個奶牛朋友們玩撲克牌，她們用了一疊有K (N ≤ K ≤ 100,000 K是N的整倍數) 張牌的撲克。這疊撲克有 M = K/N 張“好牌”和 K-M 張“壞牌”。貝茜負責給大家發牌，當然，她想把所有的好牌發給自己。她非常喜歡贏。

她們坐成一圈，逆時針方向發牌。她的朋友們懷疑她會搞鬼，於是發明瞭一個特殊的發牌規則，試圖阻止貝茜搞鬼。她們把規則列舉如下：

從貝茜的右面的奶牛開始發牌。

每發一張牌，貝茜必須把接下來的 P (1 ≤ P ≤ 10) 張牌按原順序放到這疊撲克的最後。

逆時針方向發牌，對每個人都這樣。

然而，貝茜發了瘋，不顧一切的想贏。她請你幫她設計洗牌一個方案，使她能得到所有的“好牌”。每張牌按順序標號，第一張爲#1，第二張爲#2，等等。

輸入

第 1 行: 三個整數 N , K , P

輸出

第 1..M 行: 升冪順序排列，每行爲一張好牌的位置，使得貝茜她能得到所有的“好牌”。

樣例輸入

3 9 2

樣例輸出

3

7

8

【分析】

這是一個比較簡單的隊列題，隊列不用開的很大，11,000,000就行了。

設置兩個指針，一個隊頭、一個隊尾，每次發完牌後，隊頭指針和隊尾指針都向後移動P位。發牌時，判斷這張牌是不是Bessie的（如果A%N==0，則第A張發下去的牌是Bessie的），最後把Bessie的牌按從大到小的順序快排一下，輸出即可。

這種算法的效率很高，看看我的評測結果：

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...

编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	9	0.000 s	47149 KB	0
2	正确	9	0.000 s	47149 KB	0
3	正确	9	0.000 s	47149 KB	0
4	正确	9	0.000 s	47149 KB	0
5	正确	9	0.000 s	47149 KB	0
6	正确	9	0.001 s	47149 KB	0
7	正确	9	0.003 s	47149 KB	0
8	正确	9	0.004 s	47149 KB	0
9	正确	9	0.009 s	47149 KB	0
10	正确	9	0.011 s	47149 KB	0
11	正确	9	0.193 s	47149 KB	0

运行完成

运行时间 0.223 s

平均内存使用 47149 KB

测试点通过状况 AAAAAAAAAAA

得分：100

恭喜你通过了全部测试点!

本題測試數據下載：http://ace.delos.com/TESTDATA/cheat.zip

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int Bessie[1000001];
int B=0;

int Q[11000001];
int N,P,K;
int G=0;
int q,h;

void init()
{
    scanf("%d %d %d",&N,&K,&P);
    for (int i=1;i<=K;i++)
        Q[i]=i;
    G=K/N;
}

void Put(int i)
{
    for (int j=i+1;j<=P+i;j++)
    {
        q++;
        Q[q]=Q[j];
        h++;
    }
}

int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

void Work()
{
    q=K;
    h=0;
    int tmp=0;
    while(B<G && h<=q)
    {
        h++;
        tmp++;
        if(tmp%N==0)
        {
            B++;
            Bessie[B]=Q[h];
        }
        Put(h);
    }
   
    qsort(Bessie+1,B,sizeof(int),cmp);
    for (int i=1;i<=B;i++)
        cout<<Bessie[i]<<endl;
}

int main()
{
    freopen("cheat.in","r",stdin);
    freopen("cheat.out","w",stdout);
    init();
    Work();
    return 0;
}