P9900 『PG2』消除萝卜 B 题解

· · 题解

题意简述

有 n\times2 的两列萝卜，且分为白萝卜和红萝卜。你每次可以进行以下两种操作：

  1. 花 1 的代价，选一个有萝卜的位置，将这个萝卜所在的由同种颜色萝卜构成的四连通极大连通块的萝卜全部拿走。若在第 i-1 行有一个没有萝卜的空位，则第 i 行的萝卜就会掉落至第 i-1 行。
  2. 同时你也可以花初始为 0 的代价，选定 k 而将第 k 列的所有萝卜上移，并将一个红萝卜即 1 放在第一行第 k 个，此后这个操作代价 +1。

求拿走所有萝卜的最小代价。

解题思路

题目中有一个重要的提示，即保证 a_{i,1}\ne a_{i,2}，那么操作次数通过一列即可判断。首先任选一列 k 统计 a_{i,k}\ne a_{i-1,k} 的数量，记为 t，令 a_{1,k}\ne a_{0,k}。然后很容易即可推出 answer=\lceil\frac{t}{2}\rceil+1，时间复杂度为 O(n)。

友情提示

  1. 由于本题数据较强，对于 c++ 语言，以 O(n) 的时间复杂度纯用 cin 输入都难以通过，所以可以尝试使用快读输入。 快读模板如下： 
    int read(){
int ret=0;bool sgn=false;int ch=getchar();
while(!isdigit(ch))sgn|=ch=='-',ch=getchar();//isdigit()为判断字符是否为数字的函数
while(isdigit(ch))ret=ret*10+ch-'0',ch=getchar();
return sgn?-ret:ret;//三目运算符
}
  2. 使用 inline 可以将函数定义为内联函数，有效地优化函数，感兴趣的读者可以自行上网查阅

    代码展示

    #include<bits/stdc++.h>
using namespace std;
inline int read(){//定义为内联函数
bool k=0;char c=getchar();//由于k只有一位，所以用bool类型存即可 
while(!isdigit(c))c=getchar();//k不可能为负数 
while(isdigit(c))k=c^'0',c=getchar();//k不可能进位(c^'0'等同于c-'0')
return k;
}int n,ans=1;
bool a[5000005];//只需任存一列即可 
int main(){
scanf("%d",&n),a[0]=read(),read();//第二个read()用来过滤第二列数据
for(int i=1;i<n;i++)a[i]=read(),read(),ans+=a[i]!=a[i-1];//若a[i]!=a[i-1],则ans++ 
printf("%d",1+(ans+1>>1));//输出答案(同printf("%d",1+(int)ceil(1.0*ans/2));)
return 0;
}