11363: 【原1363】changechange

题目

题目描述

author: yuan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1363 

题目描述

我记录下自己的每一天，用一个特别而有意义的方式。

如果这一刻我很无助，很愤怒，很不甘心，我就在记忆中写下一个大写字母。

如果这一刻我很快乐，很坚定，并且充满信念，我会轻轻刻下一个小写字母存在的痕迹。

我记了好长好长的时间。

终于有一天，我试图离开与改变。

首先，我要借着直觉心修改这一段带着韵律，跌宕起伏的字符。

我想寻找一个生命中重要的时间点。

在这以前，是郁郁寡欢的无知，是物质的生活，是大写字母。

在这以后，是没有条件的快乐，是心灵的感知，是小写字母。

我可以修改每一个字母，以我想要他们变成的任何形式。但是每次修改，都是对我记忆的残酷的冲击。

现在我累了，所以我想使得修改的次数最少。

现在我累了，我不想想任何事情，我也没有必要要去想这件事情。

但你不一样，你必须帮我想。那你就想想呗。

输入说明

输入一个字符串。

输出说明

输出一个整数表示最小修改次数。

样例输入1

PRuvetSTAaYA

样例输出1

5

样例输入2

OYPROSTIYAOPECHATALSYAPRIVETSTASYA

样例输出2

0

样例输入3

helloworld

样例输出3

0

数据范围

对于50%的数据，1<=字符串长度<=1000;

对于100%的数据，1<=字符串长度<=100000;

yyong119's solution

#include <iostream>
#include <cstring>
#define MAX_LEN 100010
#define min(x, y) ((x) < (y) ? (x) : (y))
using namespace std;
char str[MAX_LEN], ch;
int prev_low[MAX_LEN], fol_up[MAX_LEN];
int ans, n;
int main() {
    // input
    ios::sync_with_stdio(false);
    cin >> str;
    n = strlen(str);
    // init
    for (register int i = 1; i <= n; ++i)
        prev_low[i] = prev_low[i - 1] + (str[i - 1] >= 'a');
    for (register int i = n - 1; i >= 0; --i)
        fol_up[i] = fol_up[i + 1] + (str[i] < 'a');
    // find minimun
    ans = 0x7fffffff;
    for (register int i = 0; i <= n; ++i)
        ans = min(ans, prev_low[i] + fol_up[i]);
    cout << ans << "\n";
    return 0;
}