【Change】

2015年10月30日 0条评论 889次阅读 0人点赞

【问题描述】

我认为一个优美的字符串的任何大写字母总是在所有小写字母的前面。现在，请修改给
定的字符串，使得它变得完美。
文章的字符保证是大写字母或小写字母，一次操作定义为把一个大写字母改成小写字
母，或把一个小写字母改成大写字母。请求出最小操作次数。

【输入格式】

输入一个字符串；

【输出格式】

输出一个值表示最小操作次数；

【输入样例】

PRuvetSTAaYA

【输出样例】

【样例说明】

aim string = PRuvetSTAaYA -> PRUVETSTAAYA

【数据范围】

对 50%的输入数据：1≤字符串长度≤1000
对100%的输入数据：1≤字符串长度≤100000

对于每个位置记录一下包括它以内左边全改大写，右边全改小写需要的次数，O(n)扫一遍即可。

注意判断边界和本来就合法的情况。

下面是代码：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <algorithm>
#define inf 0x7fffffff
using namespace std;
int L[500001],R[500001],len,cont,ans=inf;
char str[500001];
void debug()
{
	for(int i=1;i<=len;i++)
	 cout<<L[i]<<" "<<R[i]<<endl;
	exit(0);
}
int main()
{
     //freopen("change.in","r",stdin);
     //freopen("change.out","w",stdout);
     scanf("%s",str+1);
     len=strlen(str+1);
     cont=0;
     for(int i=1;i<=len;i++)
      if(str[i]>='a'&&str[i]<='z')
       cont++;
     if(cont==len) {cout<<0<<endl;return 0;}
     cont=0;
     for(int i=1;i<=len;i++)
      if(str[i]>='A'&&str[i]<='Z')
       cont++;
     if(cont==len) {cout<<0<<endl;return 0;}
     cont=0;
     bool flag=false;
     for(int i=1;i<=len;i++)
     {
      if(str[i]>='a'&&str[i]<='z')
       cont++;
      if(str[i]>='A'&&str[i]<='Z'&&cont>=1)
      {
       flag=true;
       break;
      }
     }
     if(!flag) {cout<<0<<endl;return 0;} 
     for(int i=1;i<=len;i++)
     {
     	if(str[i]>='a'&&str[i]<='z')
         L[i]=L[i-1]+1;
        else
		 L[i]=L[i-1];
     }
     for(int i=len;i>=1;i--)
     {
     	if(str[i]>='A'&&str[i]<='Z')
     	  R[i]=R[i+1]+1;
        else
		 R[i]=R[i+1];
     }
     for(int i=2;i<=len-1;i++)
     	ans=min(ans,L[i-1]+R[i]);
     ans=min(ans,R[1]);
     if(str[len]>='a'&&str[len]<='z') ans=min(ans,L[len-1]);
     else ans=min(ans,L[len]);
     cout<<ans<<endl;
     return 0;
}