题目

小苯有一个长度为\(n\)的字符串\(s\)，每次操作他可以选择一个位置的字母将其的大小写反转，也就是说如果字符是小写，则操作后会变成大写，如果字符是大写则反之。
他现在希望将\(s\)变为：“前面若干字符是大写，后面的字符全是小写”的样子，例如："AABBccdd"。（注意：全大写和全小写均不合法）
请问他最少需要进行几次操作呢，请你帮帮他吧。
https://ac.nowcoder.com/acm/problem/273931

Input

输入包含一行一个字符串\(s (2 \leq |s| \leq 10^5)\)表示题中所述的字符串，保证只包含小写和大写字母。

Test1

aaBB

Test2

AAAA

Output

输出包含一行一个整数，表示最少的操作次数.

Test1

3

说明：可以将字符串变为："AABb"，操作了 3 次。

Test2

1

说明：变为："AAAa"，操作 1 次。

题解

解题思路

由题意得，本题可理解为找到一个位置，使得将小写变大写和将大写变小写的次数最少，为了保证可行的时间复杂度，可以才用前缀与后缀和预处理更改次数，再进行枚举得到最小操作数

Tips
关于大小写的一些操作：
char c='a';
if(c&' ')//判断是否为小写
if(~c&' ')//判断是否为大写
c|=' ';//转换为小写，等价于std::tolower
c^=' ';//如果原本是大写，转换为小写，原本是小写转换为大写。
c=(c|' ')^' ';//转换为大写字母，等价于std::toupper

Code

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr);
using namespace std;
typedef long long LL;

signed main(){
    IOS;
    string s;cin>>s;
    int n=s.size();
    vector<LL> pre(n+1),back(n+1);
    for(int i=1;i<n;i++){
        if(s[i-1]&' ') pre[i]=pre[i-1]+1;
        else pre[i]=pre[i-1];
    }
    
    for(int i=n-2;i>=0;i--){
        if(~s[i+1]&' ') back[i]=back[i+1]+1;
        else back[i]=back[i+1];
    }
    LL ans=8e8;
    for(int i=1;i<n-1;i++){
        ans=min(ans,pre[i]+back[i]);
    }
    cout<<ans<<endl;
    return 0;
}