联想算法题-发牌序列

联想算法题-发牌序列

问题描述

小A和小B在玩纸牌。每张牌上都有一个点数，所有的牌都背面朝上叠放成一个牌堆，现在他们在研究如何发牌。

他们研究出的发牌策略如下：小A每次将牌堆顶的那一张牌发出，每次发牌前，小B都会进行一次切牌，假设目前牌堆中有n张牌，那么小B会将前⌊n/3⌋张牌从牌堆顶依次放到牌堆底（⌊x⌋表示将x向下取整）。现在给你初始的牌堆中从顶到底每张牌的点数，请问按照上述发牌策略，最终得到的发牌序列是怎样的？

例如初始牌堆为[4, 5, 2, 3, 1, 2]（从左往右分别是牌堆中从顶到底每张牌的点数），首先小B将前⌊6/3⌋=2张牌放到牌堆底部，牌堆变为[2, 3, 1, 2, 4, 5]，然后小A将牌堆顶的2发出，牌堆变为[3, 1, 2, 4, 5]。小B再将前⌊5/3⌋=1张牌放到牌堆底部，牌堆变为[1, 2, 4, 5, 3]，然后小A及那个牌堆顶的1发出，牌堆变为[2, 4, 5, 3]……按照发牌策略继续操作后，可以得到最终的发牌序列是[2, 1, 4, 3, 2, 5]

输入描述

第一行是一个正整数n，表示初始牌堆中有n张牌。

第二行是n个正整数a_1, a_2, …, a_n，第i个数a_i表示牌堆从顶向底第i张牌的点数。

输出描述

一行n个用空格隔开的正整数b_1, b_2, …, b_n，其中b_i表示第i次发出的牌的点数。

输入样例1

6

4 5 2 3 1 2

输出样例1

2 1 4 3 2 5

数据范围和说明

30%的数据保证：1<=n<=10, 1<=a_i<=1000

80%的数据保证：1<=n<=100, 1<=a_i<=1000

100%的数据保证 ：1<=n<=1000, 1<=a_i<=1000

算法思路：

这个题的思路是模拟，通过双端队列模拟这个过程，难度不是很大。

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int main()
{
    int n;
    deque<int> a;
    vector<int> res;
    cin >> n;
    for (int i = 0; i < n; ++ i)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    while(a.size())
    {
        int m = a.size() / 3;
        vector<int> b;
        for (int i = 0; i < m; ++ i)
        {
            b.push_back(a.front());
            a.pop_front();
        }
        for (int i = 0; i < m; ++ i)
        {
            a.push_back(b[i]);    
        }
        res.push_back(a.front());
        a.pop_front();
    }
    for (int i = 0; i < res.size(); ++ i)
    {
        cout << res[i] << " ";
    }
    return 0;
}