[C++] Rotating Vote Queue


  • 0
    /**
     * Put all senate in a rotating vote queue;
     * for each senator in his turn:
     * he will either add a ban on the other party to ban their following voting senotes, if there is no ban on his own party;
     * or he will neutralize 1 ban for his own party by quit the queue permanently.
     * 
     * The queue stop rotating when there is only senate from 1 party;
     */
    
        int br = 0; // banned Radiant
        int bd = 0; // banned Dire
        int r = 0; // votable Radiant
        int d = 0; // votable Radiant
    
    class Solution {
    public:
        string predictPartyVictory(string s) {
            queue<char> q;
            int r = 0, d = 0, br = 0, bd = 0;
            for (char ch : s) {
                ch == 'R' ? r++ : d++;
                q.push(ch);
            }
            while (!q.empty() && r && d) {
                char ch = q.front();
                q.pop();
                if (ch == 'R') {
                    if (br == 0) {
                        bd++;
                        q.push(ch);
                    }
                    else {
                        br--;
                        r--;    // quit the queue
                    }
                }
                else {
                    if (bd == 0) {
                        br++;
                        q.push(ch);
                    }
                    else {
                        bd--;
                        d--;    // quit the queue
                    }
                }
            }
            return r ? "Radiant" : "Dire";
        }
    };
    

  • 0
    J

    Is there a rigorous proof of the greedy algorithm?
    I know it's the best strategy for one senate to ban the next closest senate from another party so that the banned one won't be able to ban our teammates, but that's only a rough thinking process, maybe more details and logic reasoning needed.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.