LeetCode-649-mid-Dota2 參議院 (貪心，模擬序六，詳細(xì)分析)

關(guān)鍵字：“貪心”任连、“隊(duì)列模擬”、“詳細(xì)分析”

題目描述

詳情見(jiàn)：
LeetCode-Dota2參議院

分析

對(duì)于一名參議員來(lái)說(shuō)例诀，當(dāng)投票時(shí)随抠，要禁止對(duì)方參議員的權(quán)力。
當(dāng)一方參議員全部被禁止后繁涂，另一方獲勝拱她。

要模擬這個(gè)投票過(guò)程，問(wèn)題在于每個(gè)參議員如何選擇其要禁止的敵對(duì)方參議員扔罪。那么秉沼，如何選擇呢？

貪心：選擇在自己投票后首先會(huì)進(jìn)行投票的對(duì)方參議員矿酵。
如何證明這一點(diǎn)呢唬复？

這里先給出幾個(gè)例子，直觀的認(rèn)識(shí)到順序的重要性全肮。再對(duì)該貪心策略的正確性進(jìn)行直觀分析敞咧、理論證明。

幾個(gè)例子

例子	結(jié)果
"RD"	R
"RRDDD"	R

第一個(gè)例子說(shuō)明倔矾，禁止能力的順序?qū)Y(jié)果的影響很大妄均，"RD"與"DR"的結(jié)果不同柱锹。
第二個(gè)例子說(shuō)明哪自，參議員個(gè)數(shù)更多(超過(guò)半數(shù))不一定會(huì)贏得最終結(jié)果。

分析

就一輪來(lái)說(shuō)禁熏，聯(lián)想：類(lèi)比于打牌（單升等）壤巷，假設(shè)有同一花色1-13的紙牌，雙方分別不放回的抽了數(shù)張瞧毙，如果互相知道彼此的手牌是什么胧华，假設(shè)雙方分別用 $A$ 、 $B$ 表示宙彪，對(duì)于 $A$ 矩动，其打出的手牌 $c_1$ 壓過(guò) $B$ 手牌中面值小于 $c_1$ 的最大值的手牌。

在本題中释漆，一方為R悲没，一方為D，R的目前打出的最大牌（先投票的參議員）希望將D的最大牌（D的接下來(lái)最先投票的參議員）壓過(guò)（禁止）男图。

證明

這里想要證明的是：選擇禁止對(duì)方下一個(gè)最先投票的參議員是最優(yōu)選擇示姿。

假設(shè)對(duì)方下一個(gè)最先投票的參議員的順序(index)為 $D_1$ 甜橱，如果不選擇禁止該參議員，而選擇禁止順序在其后的另一參議院栈戳，設(shè)其順序(index)為 $D_2$ 岂傲。則其他情況不變，會(huì)導(dǎo)致己方順序在 $D_1$ 到 $D_2$ 之間的參議員有了被禁止發(fā)言的威脅子檀。

解題思路

使用隊(duì)列來(lái)存儲(chǔ)各方參議員的投票順序镊掖。每方參議員按照這個(gè)貪心的思想禁止對(duì)方參議員。最后一方參議員被全部禁止就結(jié)束褂痰，得出投票結(jié)果堰乔。

算法

INPUT: string
OUTPUT: winner

// init R與D的存儲(chǔ)結(jié)構(gòu)queue
for i <- 0 to string.size :
    if string[i] == 'R'
        R_queue.push(i)
    else
        D_queue.push(i)
// 模擬整個(gè)過(guò)程的情況
for R_queue not empty ans D_queue not empty :
    //對(duì)于每輪的投票
    R_next, D_next <- [],[]
    while R_queue not empty or D_queue not empty :
        if R_queue not empty and D_queue not empty //當(dāng)兩者都有item時(shí)
            if R_queue.front() < D_queue.front() // R的參議員先投票
                D_queue.pop()
                R_next.push( R_queue.front() )
                R_queue.pop()
            else
                D_queue.pop()
                R_next.push( R_queue.front() )
                R_queue.pop()
            continue
        while R_queue not empty :
            if D_next not empty 
                D_next.pop()
            R_next.push( R_queue.front() )
            R_queue.pop()
        while D_queue not empty :
            if R_next not empty 
                R_next.pop()
            D_next.push( D_queue.front() )
            D_queue.pop()       
    R_queue <- R_next
    D_queue <- D_next
// 當(dāng)某一方為空后，投票結(jié)束
return (R_queue.empty()) ? "R" : "D"

數(shù)據(jù)結(jié)構(gòu)

在上邊的討論中脐恩，只需要用到隊(duì)列的相關(guān)功能镐侯。

代碼實(shí)現(xiàn)

class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<int> R_curr ;
        queue<int> D_curr ;

        // 數(shù)據(jù)統(tǒng)計(jì)
        for ( int i = 0 ; i < senate.size() ; ++i ){
            if ( senate[i]=='R' ){
                R_curr.push(i) ;
            }else{
                D_curr.push(i) ;
            }
        }

        while ( !R_curr.empty() && !D_curr.empty() ) {
            queue<int> R_next ;
            queue<int> D_next ;

            while ( !R_curr.empty() || !D_curr.empty() ){
                if ( !R_curr.empty() && !D_curr.empty() ){
                    if ( R_curr.front() < D_curr.front() ){
                        cout << "R" ;
                        D_curr.pop() ;
                        R_next.push( R_curr.front() ) ;
                        R_curr.pop() ;
                    }else{
                        cout << "D" ;
                        R_curr.pop() ;
                        D_next.push( D_curr.front() ) ;
                        D_curr.pop() ;
                    }
                    continue ;
                }
                //一個(gè)為空
                while ( !D_curr.empty() ){
                    if ( !R_next.empty() )
                        R_next.pop() ;
                    D_next.push( D_curr.front() );
                    D_curr.pop() ;
                }
                while ( !R_curr.empty() ){
                    if ( !D_next.empty() )
                        D_next.pop() ;
                    R_next.push( R_curr.front() );
                    R_curr.pop() ;
                }
            }
            cout << endl ;
            R_curr = R_next ;
            D_curr = D_next ;
        }
        cout << D_curr.empty() << " " << D_curr.size() << endl ;
        cout << R_curr.size() << endl ;
        return R_curr.empty() ? "Dire" : "Radiant" ;
    }
};

解題思路改良

改進(jìn)思路

對(duì)于一個(gè)排名靠前的參議員，進(jìn)行本輪禁止他人的投票后驶冒，由于對(duì)方“貪心”苟翻，所以不會(huì)被禁止。因此一定會(huì)進(jìn)入下一輪的投票中骗污，可以將多輪合并崇猫，看成是新加入一個(gè)排名靠后（比當(dāng)前所有參議員的排名都靠后）的參議員。

算法

INPUT: string
OUTPUT: winner

// init R與D的存儲(chǔ)結(jié)構(gòu)queue
for i <- 0 to string.size :
    if string[i] == 'R'
        R_queue.push(i)
    else
        D_queue.push(i)
// 模擬整個(gè)過(guò)程的情況
for R_queue not empty ans D_queue not empty:
    if R_queue.front() < D_queue.front():
        D_queue.pop()
        R_queue.push( R_queue.front()+string.size )
        R_queue.pop()
    else:
        R_queue.pop()
        D_queue.push( D_queue.front()+string.size )
        D_queue.pop()
// 判斷最終哪方為空
return (R_queue.empty()) ? "R" : "D"

代碼

class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<int> R ;
        queue<int> D ;
        int size = senate.size() ;

        // 數(shù)據(jù)統(tǒng)計(jì)
        for ( int i = 0 ; i < size ; ++i ){
            if ( senate[i]=='R' ){
                R.push(i) ;
            }else{
                D.push(i) ;
            }
        }
        // 模擬需忿，直到有一方所有參議員被禁止
        while ( !R.empty() && !D.empty() ){
            if ( R.front() < D.front() ){
                D.pop() ;
                R.push( R.front()+size ) ; // 投票后再次放進(jìn)隊(duì)列中
                R.pop() ;
            }else{
                R.pop() ;
                D.push( D.front()+size ) ;
                D.pop() ;
            }
        }
        return R.empty() ? "Dire" : "Radiant" ;
    }
};

LeetCode-649-mid-Dota2 參議院 (貪心，模擬痕钢，詳細(xì)分析)