AtCoder Tenka1 Task C: Stones

英文题面

Problem Statement

There are N stones arranged in a row. Every stone is painted white or black. A string S represents the color of the stones. The i-th stone from the left is white if the i-th character of S is ., and the stone is black if the character is #.

Takahashi wants to change the colors of some stones to black or white so that there will be no white stone immediately to the right of a black stone. Find the minimum number of stones that needs to be recolored.

Constraints

$ 1≤N≤2×10^5 $
S is a string of length N consisting of . and #.

Input

Input is given from Standard Input in the following format:
N
S

Output

Print the minimum number of stones that needs to be recolored.

Sample Input 1

3
#.#

Sample Output 1

1

It is enough to change the color of the first stone to white.

Sample Input 2

5
#.##.

Sample Output 2

2

Sample Input 3

9
.........

Sample Output 3

0

中文题面(人工翻译)

有N块石头连续排列。每块石头都被涂成白色或黑色。字符串S中的每一个元素代表每一块石头的颜色。如果S的第i个字符是'.'时,那么左边的第i块石头是白色的,如果时'#'时,那块石头是黑色的。

Takahashi想要将一些石头的颜色从黑色改为白色或从白色改为黑色,这样就不会在黑色石头的右边出现白色的石头。求出使得上述条件成立的重新涂色的最小石头数。

数据范围

1≤n≤2×10^5

S是一个仅包含'#'和'.'的字符串

输入

输入由标准输入以下列格式给出:

N
S

输出

打印需要重新着色的最小数量的宝石。

样例输入1

3
#.#

样例输出1

1

将第一块石头的颜色改为白色就足够了。

样例输入2

5
#.##.

样例输出2

2

样例输入3

9
.........

样例输出3

0

解题思路

这是一道非常巧妙的前缀和的题目,当然也可以不用前缀和做

这道题目的意思其实就是从某一块石头开始左边全是白色,右边全是黑色。所以我们只需要枚举每一块石头左边的黑色石头的数量加上右边白色石头数量,然后求出最小值即可。

向普及组的OIER们推荐这道题目

代码

#include <iostream>
#include <cstring>
using namespace std;
int cntw[500000],cntb[500000];
int main(){
    int n;
    cin>>n;
    char s[500000];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    memset(cntw,0,sizeof(cntw));
    memset(cntb,0,sizeof(cntb));
        //前缀和,枚举每一个位置以及之前的黑色石头数与白色石头数。
    for(int i=0;i<n;i++){
        if(s[i]=='.'){
            cntw[i+1]=cntw[i]+1;
            cntb[i+1]=cntb[i];
        }else{
            cntb[i+1]=cntb[i]+1;
            cntw[i+1]=cntw[i];
        } 
    }
        //寻找最小值。
    int minn=1000000;
    for(int i=0;i<=n;i++){
        if(cntb[i]+cntw[n]-cntw[i]<=minn){
            minn=cntb[i]+cntw[n]-cntw[i];
        }
    }
/*    for(int i=0;i<n;i++){
        cout<<cntw[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<n;i++){
        cout<<cntb[i]<<" ";
    }
*/    cout<<minn;
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/346/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者