網易有道2017内推程式設計題2

題目描述：

小明同學把1到n這n個數字按照一定的順序放入了一個隊列Q中。現在他對隊列Q執行了如下程式：

while (!Q.empty()) //隊列不空，執行循環

{

int x = Q.front(); //取出目前隊頭的值x

Q.pop(); //彈出目前隊頭

Q.push(x); //把x放入隊尾

x = Q.front(); //取出這時候隊頭的值

printf("%d\n", x); //輸出x

Q.pop(); //彈出這時候的隊頭

}
           

做取出隊頭的值操作的時候，并不彈出目前隊頭。

小明同學發現，這段程式恰好按順序輸出了1, 2, 3, …, n。現在小明想讓你構造出原始的隊列，你能做到嗎？[注：原題樣例第三行5有錯，應該為3，以下已修正]

輸入描述:

第一行一個整數T（T ≤ 100）表示資料組數，每組資料輸入一個數n（1 ≤ n ≤ 100000），輸入的所有n之和不超過200000。

輸出描述 :

對于每組資料，輸出一行，表示原始的隊列。數字之間用一個空格隔開，不要在行末輸出多餘的空格.

輸入例子1 :

4

1

2

3

10

輸出例子1 :

1

2 1

2 1 3

8 1 6 2 10 3 7 4 9 5

解題思路：

方案一：

按照取出資料規則，每存一個資料，跳過一個空位置，在下一個空位置放置

方案二：

對比小明取出規則，反着存資料

代碼實作：

#include <iostream>
#include <vector>
#include <deque>
using namespace std;


int main()
{
    int group;
    cin >> group;
    while (group--)
    {
        int n;
        cin >> n;
        

        //指派方法一
        //vector<int>v(n, 0);
        //for (int ptr = -1, m = 1; m <= n; ++m)
        //{
        //    do
        //    {
        //        ++ptr;//跳過一個
        //        if (ptr >= n)
        //            ptr = 0;
        //    } while (v[ptr] != 0);
        //    do
        //    {
        //        ++ptr;//選擇下一個
        //        if (ptr >= n)
        //            ptr = 0;
        //    } while (v[ptr] != 0);
        //    v[ptr] = m;            
        //}
        //指派方法二
        deque<int> v;
        for (int i = n; i > 0; --i)
        {
            v.push_front(i);
            int t = v.back();
            v.pop_back();
            v.push_front(t);
        }


        for (auto a : v)
            cout << a << ' ';
        cout << endl;
    }

    return 0;
}
           

後記

個人部落格位址：

一筆一畫一人生

個人原創： 轉載請說明！