牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG或RRRRR就满足要求了,涂染的个数都为2,没有涂染个数更少的方案了。
输入包括一个字符串s,字符串s长度length(1 ≤ length ≤ 50),其中只包括'R'或者'G',分别表示红色和绿色。
输出一个整数,表示牛牛最少需要涂染的正方形数量
RGRGR
2
GGGGRRR
3
可以将GGGGRRR涂染成GGGGGGG,所以最少需要涂染3个正方形。
#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; }
package main import ( "fmt" "math" ) func main() { var input string fmt.Scan(&input) resultCount, gCount := 0, 0 for _, s := range []byte(input) { if s == 'R' { // 往右走碰到R则需要改变,或者改变之前的G,两者取最小的方案 resultCount = int(math.Min(float64(resultCount+1), float64(gCount))) }else { // 碰到G,则记录起来 gCount++ } } fmt.Println(resultCount) }
其实这题就是把最后结果变成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; }
#include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; int n = s.size(); int ans = INT_MAX; for (int i = 0; i <= n; i += 1) { int cnt = 0; for (int j = 0; j < i; j += 1) { if (s[j] == 'G') { cnt += 1; } } for (int j = i; j < n; j += 1) { if (s[j] == 'R') { cnt += 1; } } ans = min(ans, cnt); } cout << ans; }
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); } }
#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++);//去掉头部的Rp = s + i;n = strlen(p);for(i = n - 1; i >= 0 && 'G'== p[i]; i--);//去掉尾部的Gn = 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;}