Codeforces 430B Balls Game（Two Pointers）
forever97
posted @ 2016年7月25日 17:00
in 算法-Two pointers
with tags
Two pointers
, 734 阅读
【题目链接】 http://codeforces.com/contest/430/problem/B
【题目大意】
祖玛游戏，给出一个序列，表示祖玛球的颜色序列，三个或者以上的球碰在一起就会发生消除，现在有一个颜色为x的球，问最多可以消除多少球。
【题解】
消除的球一定是连续的一段，因此我们可以枚举球射入的位置，然后向两边扩展，每次在已扩展的序列两边有三个相同颜色的球才能继续扩展，否则就停止，取每次枚举的最大值就是答案。
【代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k,x,ans,t[105];
int main(){
scanf("%d%d%d",&n,&k,&x);
for(int i=1;i<=n;i++)scanf("%d",&t[i]);
for(int i=0;i<=n;i++){
int L=i,R=i+1,cnt=1,cur=x,preL,preR;
while(1){
preL=L,preR=R;
while(L&&t[L]==cur){L--;cnt++;}
while(R<=n&&t[R]==cur){R++;cnt++;}
if(cnt<=2){L=preL;R=preR;break;}else cur=t[L],cnt=0;
}ans=max(ans,R-L-1);
}printf("%d",ans);
return 0;
}
评论 (0)
