Codeforces 1397D - Stoned Game(暴力搜尋 Brute force)

題目大意：

T、HL 在玩遊戲。遊戲規則如下，有 x 堆石頭，每堆石頭數量不定，每次都是 T 先從其中一堆拿石頭，H 再拿一顆石頭，每位玩家則不可以拿上位玩家拿石頭的石頭堆。
這到底是甚麼原始人遊戲 XD，好像舊石器時代的人會玩的遊戲

分析：

這題真的很難啊…，這題目與我之前碰過的經驗不同，讓我搞錯方向去思考，好題好題。
幸好有解開啦…，不然我就會很生氣了 XD。

每次都選擇最大的兩堆石頭出來，然後兩堆石頭各減一。之後再放回去 priority_queue 內，假如 priority_queue size 只有一堆代表 T win，若剛好 0 堆則代表 HL win。

至於我為甚麼會這樣想呢？我建議讀者都先從我的初步想法慢慢讀起，我認為會比直接看我的正確想法來的更好理解些。

初步想法

錯誤想法 - 奇偶數堆

一開始，稍微推斷一下。
他可能是甚麼透過偶奇數來判斷的，個人在猜應該是用偶數堆與奇數堆來進行判斷。
後來自己在紙筆推導時，發現 2 2 2 這測資是 HL win。但 2 2 4 則是 T 贏。

錯誤想法 - T 從最小堆石頭拿取，HL 從最大堆石頭拿取

這是根據題目給的測資進行判斷，比較有點根據了XD
只要只剩一堆石頭必定會是 T 贏，HL 則是要盡量讓石頭堆數達到兩堆且兩堆數量一樣。(從題目測資進行判斷)，於是我寫了一程式關於 T 從小石頭開始拿，當 T 從小石頭堆的提取數量已經大於 HL 的最大堆時，則 HL 在往次大堆進行提取，看最後是 T 還是 HL 的石頭比較多，我在進行判斷。(此想法透過遞迴撰寫)。

由於是錯誤想法因此我用圖片來給大家看我的錯誤遞迴，以免誤導大家以為這也是正確的一部份。

但後來證明我是錯誤的，測資怎麼樣都沒過，卡在第二筆。我後來仔細想想，每次都只拿一顆，經驗告訴我，消去法不一定適用。在使用 2 2 2 測資時得到啟發。

正確想法 - T 只提取最大堆石頭，HL 則提取次大堆石頭

為甚麼會這樣想呢？ 是 1 5 1 這測資啟發我的，我只要 T 直接拿取最大堆，那 HL 要拿甚麼石頭我都不需要在意阿 XD，反正我只要拿我的最大堆，剩下的石頭隨 HL 拿就行。那如果最大堆沒有呢？那就拿次大堆吧，把問題丟給 HL 就可以了 XD。

那有人會好奇說，為甚麼 HL 怎麼會每次都拿最大堆石頭？這樣 HL 真的是聰明的嗎？其實阿，這場遊戲 HL 完全沒有優勢，她為了要把自己的優勢找回來，所以她要拿次大堆的石頭，來希望當最大堆的石頭用完時，次大堆的石頭還在，這樣他就會是贏家 XD。

心得：

暴力解法，這題讓我很意外啊！我以為會是很優秀的解法，沒想到被我這個程式笨蛋給用暴力解法解出來，如果這並不是作者想的方法，作者會被我給氣死吧! XD

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 120
using namespace std;
int t , n ;
priority_queue<int> num;
int a , b ;

void judge(){
    int a , b ;
    while(num.size()){
        a = num.top() ;
        a-- ;
        num.pop();
        if(!num.size()){
            cout << "T" << '\n' ;
            return ;
        }

        b = num.top() ;
        b-- ;
        num.pop();
        if(a > 0)
            num.push(a);
        if(b > 0)
            num.push(b);
    }
    cout << "HL" << '\n' ;
}

int main()
{
//#ifdef LOCAL
//    freopen("in1.txt" , "r" , stdin );
//#endif // LOCAL
    cin >> t ;
    while(t--){
        cin >> n ;
        int intTemp ;
        for(int i = 0 ; i < n ; i++){
            cin >> intTemp ;
            num.push(intTemp) ;
        }
        judge();
    }
    return 0;
}