12899 Stones

题意

你可以更改一个位置的属性(. 或 #),使得没有.在#的右侧( . 不能直接在 # 右侧, # 右侧必然还是 # , . 也就不能在后面那个 # 的右侧,故所有的 . 都在 # 左侧才行)

方法

遍历每一个位置,将它左侧的 # 变成 . ,右侧的 . 变成 # ,求每个位置需要的最少操作次数。
因此可以求前缀和代表左侧 # 的个数,求后缀和代表右侧 . 的个数,遍历时二者相加就是该位置所需的操作步数。

代码

想的有些急了,将连续的同色块合并才求的前缀后缀和,其实可以简化代码。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e6+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
char s[N];
int d[N],e[N];
int l[N],r[N];
int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    d[1]=1;
    e[1]=(s[1]=='.'?0:1);
    int k=1;
    for(int i=2;i<=n;i++)
    {
        if(s[i]==s[i-1])
        {
            d[k]++;
        }
        else
        {
            k++;
            d[k]=1;
            e[k]=(s[i]=='.'?0:1);
        }
    }
    for(int i=(e[1]==0?2:1);i<=k;i+=2)
    {
        l[i]=l[i-2]+d[i];
    }
    for(int i=(e[k]==0?k:k-1);i>0;i-=2)
    {
        r[i]=r[i+2]+d[i];
    }
    int ans=inf;
    for(int i=1;i<=k;i++)
    {
        if(e[i]==1)
        {
            ans=min(ans,l[i-2]+r[i+1]);
        }
        else
        {
            ans=min(ans,l[i-1]+r[i+2]);
        }
    }
    printf("%d",ans);
    return 0;
}

简化后的:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e6+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
char s[N];
int l[N],r[N];
int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++)
        l[i]=l[i-1]+(s[i]=='#');
    for(int i=n;i>=1;i--)
        r[i]=r[i+1]+(s[i]=='.');
    int ans=inf;
    for(int i=1;i<=n;i++)
        ans=min(ans,l[i-1]+r[i+1]);
    printf("%d",ans);
    return 0;
}