首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#12990

博弈游戏 题目描述 两位玩家进行回合制博弈游戏,游戏总计进行 n 轮。每一轮,双方都要从1、2、3三个数字中选择一个出招,胜负规则如下: (1)若双方选择的数字…

博弈游戏

题目描述

两位玩家进行回合制博弈游戏,游戏总计进行 n 轮。每一轮,双方都要从1、2、3三个数字中选择一个出招,胜负规则如下:

(1)若双方选择的数字相同,本轮为平局;

(2)若数字不同,胜负遵循固定克制关系:1克制2,2克制3,3克制1,被克制的一方本轮落败,克制的一方本轮获胜。

其中一位玩家提前掌握了对手的完整出招顺序——对手在第 i 轮选择的数字为 si,所有 si 组成一个长度为 n 的序列。

该玩家需要规划自己每一轮的出招,满足以下全部条件:

(1)任何一轮都不能落败(即每一轮只能获胜或平局);

(2)不能连续两轮选择相同的数字出招;

(3)在满足前两个条件的前提下,尽可能多地获得轮次的胜利。

请计算该玩家最多能赢得的轮次数量。

输入格式

第一行:一个整数表示n。

第二行:n 个整数,表示s1、s2、……、sn,每个数为1、2或3。

输出格式

输出一个整数,表示玩家最多能赢得的游戏轮数。

输入样例#1

6
3 1 2 2 1 2

输出样例#1

5

输入样例#2

24
2 3 1 3 2 1 1 1 1 1 3 3 1 3 1 3 2 2 1 2 3 1 2 2

输出样例#2

18

说明提示:

1≤n≤200,000,si∈{1,2,3}

限制:

时间限制:1000ms,内存限制:256MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     int n;     cin &gt;&gt; n;     vector&lt;int&gt; s(n);     for (int i = 0; i &lt; n; ++i) {         cin &gt;&gt; s[i];     }     int ans = 0;     int last = 0; // 上一轮出的数     for (int x : s) {         int win;    // 能赢的数         int draw = x; // 能平的数         // 计算克制关系:1克2,2克3,3克1         if (x == 1) win = 3;         else if (x == 2) win = 1;         else win = 2;         // 优先选赢的,只要不和上一轮重复         if (win != last) {             ans++;             last = win;         }         // 不能赢 → 只能平         else {             last = draw;         }     }     cout &lt;&lt; ans &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。