AtCoder Beginner Contest竞赛题解 | 洛谷 AT_abc438_c 1D puyopuyo

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总

【题目来源】

洛谷：[AT_abc438_c ABC438C] 1D puyopuyo - 洛谷

【题目描述】

给定一个长度为N NN的整数序列A = ( A 1 , A 2 , … , A N ) A=(A_1,A_2,\ldots,A_N)A=(A1​,A2​,…,AN​)。

你可以执行以下操作零次或多次（任意顺序，任意次数）：

· 选择一个整数k kk满足1 ≤ k ≤ ∣ A ∣ − 3 且 A k = A k + 1 = A k + 2 = A k + 3 1 \leq k \leq |A|-3 且 A_k=A_{k+1}=A_{k+2}=A_{k+3}1≤k≤∣A∣−3且Ak​=Ak+1​=Ak+2​=Ak+3​，然后从A AA中删除A k , A k + 1 , A k + 2 , A k + 3 A_k,A_{k+1},A_{k+2},A_{k+3}Ak​,Ak+1​,Ak+2​,Ak+3​。（更准确地说，将A AA替换为( A 1 , A 2 , … , A k − 1 , A k + 4 , A k + 5 , … , A N ) (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N)(A1​,A2​,…,Ak−1​,Ak+4​,Ak+5​,…,AN​)。）

这里，∣ A ∣ |A|∣A∣表示整数序列A AA的长度。

求重复进行操作后，最终∣ A ∣ |A|∣A∣可能的最小值。

【输入】

输入以以下格式从标准输入给出：

N A 1 A 2 … A N N A_1 A_2 \ldots A_NNA1​A2​…AN​

【输出】

输出重复进行操作后，最终∣ A ∣ |A|∣A∣可能的最小值。

【输入样例】

10 1 1 1 4 4 4 4 1 2 3

【输出样例】

2

【算法标签】

《洛谷 AT_abc438_c 1D puyopuyo》 #贪心# #栈#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;typedefpair<int,int>PII;// 定义pair类型，first存储颜色，second存储连续个数intn;// 彩珠总数stack<PII>st;// 栈，存储{颜色, 连续个数}intmain(){// 输入彩珠总数cin>>n;// 处理每个彩珠for(inti=1;i<=n;i++){intx;// 当前彩珠的颜色cin>>x;// 如果栈为空 或 当前颜色与栈顶颜色不同if(st.empty()||x!=st.top().first){// 新颜色入栈，连续个数为1st.push({x,1});}// 如果当前颜色与栈顶颜色相同elseif(x==st.top().first){// 栈顶颜色的连续个数加1st.top().second++;// 如果连续个数达到4，消除这4个连续的彩珠if(st.top().second==4){st.pop();}}}// 计算消除后剩余的彩珠总数intans=0;while(!st.empty()){// 累加每个颜色段剩余的彩珠数ans+=st.top().second;st.pop();}// 输出剩余彩珠数cout<<ans<<endl;return0;}

【运行结果】

10 1 1 1 4 4 4 4 1 2 3 2