思路:只要遍历一次,分别统计左侧的g的数量和右侧r的数量,就可以得到染色的次数。
代码如下:
#include<string>#include<iostream>#include<vector>#include<algorithm>using namespace std;int gettimes(string str){ int rsum = 0; int gsum = 0; for (int i = 0; i != str.length(); ++ i){ if (str[i] == 'R')rsum++; if (str[i] == 'G')gsum++; } vector<int> res; int left = 0;//左侧g的数量 int right = rsum;//右侧r的数量 res.push_back(rsum); res.push_back(gsum); for (int i = 0; i != str.length(); ++i){ if (str[i] == 'R'){ right--; res.push_back(left + right); } else if (str[i] == 'G'){ left++; res.push_back(left + right); } } int a = res[min(res.begin(), res.end())-res.begin()]; return a;}int _tmain(int argc, _TCHAR* argv[]){ int a = gettimes("GGGGGRGGRGRRR"); cout << a << endl; return 0;}