关键字：“贪心”、“队列模拟”、“详细分析”
题目描述
详情见：
LeetCode-Dota2参议院
分析
- 对于一名参议员来说，当投票时，要禁止对方参议员的权力。
- 当一方参议员全部被禁止后，另一方获胜。
要模拟这个投票过程，问题在于每个参议员如何选择其要禁止的敌对方参议员。那么，如何选择呢？
贪心：选择在自己投票后首先会进行投票的对方参议员。
如何证明这一点呢？
这里先给出几个例子，直观的认识到顺序的重要性。再对该贪心策略的正确性进行直观分析、理论证明。
几个例子
| 例子 | 结果 |
|---|---|
| "RD" | R |
| "RRDDD" | R |
第一个例子说明，禁止能力的顺序对结果的影响很大，"RD"与"DR"的结果不同。
第二个例子说明，参议员个数更多(超过半数)不一定会赢得最终结果。
分析
就一轮来说，联想：类比于打牌（单升等），假设有同一花色1-13的纸牌，双方分别不放回的抽了数张，如果互相知道彼此的手牌是什么，假设双方分别用、
表示，对于
，其打出的手牌
压过
手牌中面值小于
的最大值的手牌。
在本题中，一方为R，一方为D，R的目前打出的最大牌（先投票的参议员）希望将D的最大牌（D的接下来最先投票的参议员）压过（禁止）。
证明
这里想要证明的是：选择禁止对方下一个最先投票的参议员是最优选择。
假设对方下一个最先投票的参议员的顺序(index)为，如果不选择禁止该参议员，而选择禁止顺序在其后的另一参议院，设其顺序(index)为
。则其他情况不变，会导致己方顺序在
到
之间的参议员有了被禁止发言的威胁。
解题思路
使用队列来存储各方参议员的投票顺序。每方参议员按照这个贪心的思想禁止对方参议员。最后一方参议员被全部禁止就结束，得出投票结果。
算法
INPUT: string
OUTPUT: winner
// init R与D的存储结构queue
for i <- 0 to string.size :
if string[i] == 'R'
R_queue.push(i)
else
D_queue.push(i)
// 模拟整个过程的情况
for R_queue not empty ans D_queue not empty :
//对于每轮的投票
R_next, D_next <- [],[]
while R_queue not empty or D_queue not empty :
if R_queue not empty and D_queue not empty //当两者都有item时
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
// 当某一方为空后，投票结束
return (R_queue.empty()) ? "R" : "D"
数据结构
在上边的讨论中，只需要用到队列的相关功能。
代码实现
class Solution {
public:
string predictPartyVictory(string senate) {
queue<int> R_curr ;
queue<int> D_curr ;
// 数据统计
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 ;
}
//一个为空
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" ;
}
};
解题思路改良
改进思路
对于一个排名靠前的参议员，进行本轮禁止他人的投票后，由于对方“贪心”，所以不会被禁止。因此一定会进入下一轮的投票中，可以将多轮合并，看成是新加入一个排名靠后（比当前所有参议员的排名都靠后）的参议员。
算法
INPUT: string
OUTPUT: winner
// init R与D的存储结构queue
for i <- 0 to string.size :
if string[i] == 'R'
R_queue.push(i)
else
D_queue.push(i)
// 模拟整个过程的情况
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() ;
// 数据统计
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 ) ; // 投票后再次放进队列中
R.pop() ;
}else{
R.pop() ;
D.push( D.front()+size ) ;
D.pop() ;
}
}
return R.empty() ? "Dire" : "Radiant" ;
}
};
相关问题
待补充
PS.
相比较于其他已有的leetcode刷题笔记，我希望能够提供相关的解题分析和部分相关问题的链接，使得大家能获得一个较好的分析与相关问题的比较。
偶尔会进行类似题目的总结工作，有需要的读者可以对这份工作进行关注。
如果你发现有相关的错误或者表述不当不清晰的地方，请进行评论，我会尽快进行核对勘正。
