红和绿

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s;

int work(string t){
    int ans=0;
    for(int i=0;i<(int)t.size();i++){
        if(s[i]!=t[i])  ans++;
    }
    return ans;
}

int main(void){
    cin >> s;
    int ans=INT_MAX;
    for(int cntR=0;cntR<=(int)s.size();cntR++){
        string t="";
        for(int i=1;i<=cntR;i++) t+='R';
        for(int i=1;i<=(int)s.size()-cntR;i++) t+='G';
        ans=min(ans,work(t));
    }
    cout << ans << endl;

    return 0;
}

	

其实这题就是把最后结果变成R...RG..G的样子，那就好说了，假设从左边第一个开始为RG分界点，依次往右遍历，每个位置遍历一次。不过这样复杂度为O(n^2)，那就先计算所有RG个数，每碰到一个R就把g2r-1，碰到一个G就r2g+1，这样就不需要每个位置都计算修改个数了，复杂度也就成了O(n)。
int redandgreen_137842(string in)
{
    int r2g=0, g2r=0;
    int r=0, g=0;
    for(int i=0;i<in.size();i++)
    {
        if(in[i]=='R')
            r++;
        else
            g++;
    }
    r2g=r;
    int min=r2g+g2r;
    for(int i=0;i<in.size();i++)
    {
        if(in[i]=='G')
        {
            g2r++;
        }
        if(in[i]=='R')
        {
            r2g--;
        }
        if(g2r+r2g<min)
            min=g2r+r2g;
    }
    return min;
}

int main() {
    string s;
    cin >> s;
    
    int green = 0, red = 0;
    
    for (char c : s) {
        if (c == 'R') red++;
    }
    
    int count = red;
    
    for (char c : s) {
        if (c == 'R') red--;
        else green++;
        count = min(count, red + green);
    }
    
    cout << count;
    
    return 0;
}

e & 0x1

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);       
        char[] q = in.nextLine().toCharArray();
        int a = 0,b = 0,c = 0,d = 0;c = 50;
        for(char e : q){            
            a += d = e & 0x1;
            b += d ^ 0x1;
            c = Math.min(a-b,c);
        }
        d = Math.min(Math.min(a,b),b+c);
        System.out.println(d);
    }
}

s = input()
r = 0
r_need = 0
for i in s:
    if (i == 'R'):
        r += 1
for i in range(r):
    if (s[i] == 'G'):
        r_need += 1
print(r_need*2)

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
string str = "";
getline(cin, str);
int size = str.size();
vector<int>ldp(size, 0);
vector<int>rdp(size, 0);
// 填写当前ldp中当前数左边的G的个数
int l=0;
for(int i=0; i<size; ++i)
{
ldp[i] = l;
if(str[i] == 'G')
++l;
}
// 填写当前rdp中当前数右边的R的个数
int r=0;
for(int i=size-1; i>=0; --i)
{
rdp[i] = r;
if(str[i] == 'R')
++r;
}
// 开始计算
int res = 100;
for(int i=0; i<size; ++i)
{
if(ldp[i] + rdp[i] < res)
res = ldp[i] + rdp[i];
}
cout << res << endl;
return 0;
}

#include <iostream>
using namespace std;
int main() {
    string s;
    int r[55],g[55];
    while(cin>>s){
        r[0]=g[0]=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='R'){
                r[i+1]=r[i]+1;
                g[i+1]=g[i];
            }else{
                r[i+1]=r[i];
                g[i+1]=g[i]+1;
            }
        }
        ///统计R和G的数量
        int sumR=r[s.size()];
        int sumG=g[s.size()];
        ///最坏情况，就是把R全变为G或者把G全部变为R
        int res=min(sumR,sumG);
        for(int i=1;i<=s.size();i++){
            ///遍历每个点需要修改的数量，记录最小值即可
            res=min(res,g[i]+sumR-r[i]);
        }
        cout<<res<<endl;
    }
    return 0;
}

	#include<stdio.h>



	#include<string.h>



	intmain()



	{



	    intr = 0, i = 0, n, min = 50, r2 = 0, g2 = 0, x;



	    chars[51], *p;



	    gets(s);



	    for(i = 0; 'R'== s[i]; i++);//去掉头部的R



	    p = s + i;



	    n = strlen(p);



	    for(i = n - 1; i >= 0 && 'G'== p[i]; i--);//去掉尾部的G



	    n = i + 1;



	    //统计r的数量，其实应该放到下面的else里面



	    for(i = 0; i < n; i++)



	    {



	        if('R'== p[i])



	        {



	            r++;



	        }



	    }



	    if(0 == n)



	    {



	        min = 0;



	    }



	    else



	    {



	        for(i = 0; i < n; i++)



	        {



	            //统计0 ~ i 的r和g的数量



	            if('R'== p[i])



	            {



	                r2++;



	            }



	            else



	            {



	                g2++;



	            }



	            x = g2 + r - r2;//以i为界限，左涂g右涂r的数量



	            min > x && (min = x);



	        }



	    }



	    //考虑全涂成一色的情况



	    if(r < min)



	    {



	        min = r;



	    }



	    if(n - r < min)



	    {



	        min = n - r;



	    }



	    printf("%d", min);



	    return0;



	}