题解：P10331 [UESTCPC 2024] 消消乐

xiaoliebao1115 · 2024-05-16 18:58:34 · 题解

大体思路

计算出连续的 0 和 1 的个数，记为 a 数组，根据这些数以两个为分界点求解，分最大值、最小值两种情况讨论。

求连续的 0 和 1 的个数是这样，下文 a 数组大小记为 cnt。

for(int i=0;i<s.size();i++)
{
    if(s[i]!=s[i-1]) 
    {
        cnt++;
        a[cnt]=1;
    }
    else a[cnt]++;
}

最大值

找到与 a 数组端点最接近的大于等于 2 的数，从该数出发一直操作即可。

int ansmax=0;
for(int i=1;i<=cnt;i++)
{
    if(a[i]>=2)
     ansmax=max(ansmax,max(i,cnt-i+1));
}

最小值

最小值的理论下界是除了第一次操作和最后一次操作外，保证一次操作删掉两个数，也就是 cnt\div 2+1 。

分两类讨论：能达到理论下界或不能。

当 a 数组中有一段连续的 1 长度过大时就不能，可以分在边缘和不在边缘两种情况讨论，具体可见代码。

if(i==sum||i==cnt)//边缘
{
    if(sum>cnt-sum-1) ansmin=sum+1;
  //如何判断长度过大以及答案
    continue;
}
//非边缘
if(sum>cnt-sum-2) ansmin=sum+2;
//如何判断长度过大以及答案

剩下的长度小一点的一定可以达到理论下界，因为找到最靠近中间点的两个大于等于 2 的数，一定可以对这两个数进行操作使得这两个数到边缘剩下的距离相等。

//sum 是连续 1 的长度
int sum=0,ansmin=INT_MAX;
for(int i=1;i<=cnt;i++)
{
    if(a[i]==1) sum++;
    else sum=0;
    //此处省略判断长度过大的代码
}
if(ansmin==INT_MAX) ansmin=cnt/2+1;

最后要特判 a 数组都为 1 的情况，这种情况无法操作，其他情况都可以将数组删至只剩一个数。