Giả sử trong thế giới của Dota2, có hai đảng - The Radiant và Dire. Thượng viện Dota2 bao gồm các thượng nghị sĩ đến từ hai đảng. Bây giờ thượng viện muốn đưa ra một sự lựa chọn một vài thay đổi trong trò chơi Dota2. Việc bỏ phiếu cho sự thay đổi này có thể là một thủ tục vòng tròn. Trong mỗi hiệp đấu, mỗi thượng nghị sĩ có thể thực hiện một trong hai quyền -
-
Cấm một thượng nghị sĩ quyền - Một thượng nghị sĩ có thể khiến một thượng nghị sĩ khác mất tất cả các quyền của mình trong thời gian này và mọi quyền trong các vòng tiếp theo.
-
Thông báo chiến thắng - Nếu thượng nghị sĩ này nhận thấy các thượng nghị sĩ vẫn có quyền bỏ phiếu đều thuộc một đảng tương đương, anh ta có thể thông báo chiến thắng và đưa ra lựa chọn về sự thay đổi trong trò chơi.
Đưa ra một chuỗi đại diện cho mỗi đảng của thượng nghị sĩ. Ký tự 'R' và 'D' lần lượt đại diện cho nhóm Radiant và cả nhóm Dire. Sau đó, nếu có n thượng nghị sĩ, kích thước của chuỗi đã cho sẽ là n.
Thủ tục theo vòng bắt đầu từ thượng nghị sĩ sơ cấp đến thượng nghị sĩ cuối cùng theo thứ tự nhất định. Thủ tục này sẽ kéo dài cho đến đỉnh của cuộc bỏ phiếu. Tất cả các thượng nghị sĩ bị mất quyền sẽ bị bỏ qua trong thủ tục.
Giả sử mọi thượng nghị sĩ đủ nhạy bén và có thể chơi chiến lược đơn giản nhất cho nhóm của mình, bạn muốn dự đoán xem cuối cùng bên nào sẽ công bố chiến thắng và thực hiện thay đổi trong trò chơi Dota2. Đầu ra phải là Radiant hoặc Dire.
Vì vậy, nếu đầu vào giống như "RDD", nó sẽ là Dire. Điều này là do thượng nghị sĩ đầu tiên đến từ Radiant và anh ta chỉ có thể cấm quyền của thượng nghị sĩ tiếp theo trong vòng 1. Và thượng nghị sĩ thứ hai không thể thực hiện bất kỳ quyền nào nữa vì quyền của anh ta đã bị cấm. Sau đó, thượng nghị sĩ thứ ba đến từ Dire và anh ta có thể cấm quyền của thượng nghị sĩ đầu tiên ở vòng 1. Bây giờ ở vòng 2, thượng nghị sĩ thứ ba chỉ có thể công bố chiến thắng vì anh ta là người duy nhất trong thượng viện có thể bỏ phiếu.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Tạo hàng đợi q1, q2, n:=kích thước của chuỗi. Đối với tất cả R, chèn vào q1 và với tất cả D, chèn vào q2.
-
trong khi cả hai hàng đợi đều không trống
-
nếu phần tử phía trước của q1
-
chèn n vào q1, xóa khỏi q2 và q1
-
-
nếu không thì chèn n vào q2, xóa khỏi q2 và q1
-
tăng n lên 1
-
-
nếu hàng đợi trống, thì trả về Dire, ngược lại, trả về Radiant
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string predictPartyVictory(string s) {
queue <int> q1, q2;
int n = s.size();
for(int i = 0; i < s.size(); i++){
if(s[i] == 'R'){
q1.push(i);
} else {
q2.push(i);
}
}
while(q1.size() && q2.size()){
if(q1.front() < q2.front()){
q1.push(n);
q2.pop();
q1.pop();
} else {
q2.push(n);
q2.pop();
q1.pop();
}
n++;
}
return q1.empty()? "Dire" : "Radiant";
}
};
main(){
Solution ob;
cout <<(ob.predictPartyVictory("RDD"));
} Đầu vào
"RDD"
Đầu ra
Dire