11-3. 反転文字列

1476 ワード
greedy 白駿 ps テキストリンク
この問題の本にもあるし、白俊にも同じ問題がある.
白俊1439号です。反転
1.質問
マルチシスは、0と1のみからなる文字列Sを有する.多順はこの文字列Sのすべての数字を同じにしたいと思っています.マルチシスはSの連続する1つ以上の数字をつかんで、それからすべてひっくり返すことができます.反転は1を0に、0を1にすることを意味します.
例えば、S=0001100の場合、
全体的にひっくり返すと1110011です.
4文字目から5文字目を反転すると111111になり、2文字目ですべて同じ数字になります.
ただし、最初から4文字目から5文字目に文字を反転させると、1回に1億円に変換でき、1回目ですべて同じ数字に変換できます.
文字列Sが指定されている場合は、マルチシスが実行しなければならない最小操作回数を出力します.
2.入力
最初の行は文字列Sを与える.Sの長さは100万未満である.
3.出力
最初の行は多順で行うべき最小限の行動回数を出力します.
4.解答
  • 全体を0に変換した場合、全体を1に変換した場合、最高値を探します.
  • cntを追加する範囲を探す必要があり,前後で比較した.
    • 5.最初のコードと異なる点
  • はありません.
  • の答えとは異なり、cntを増やしたときはiかi+1かです.どうせiが0ならi+1が1だから大丈夫
  • 念のため、百駿に提出しましたが、通過しました.
    • 6.解答
    #include <iostream>
#include <algorithm>

using namespace std;

int main(){
	string s;
	cin>>s;
	
	int  cnt_zero=0, cnt_one=0;
	if(s[0]=='0') cnt_one++;
	else cnt_zero++;
	
	for(int i=0; i<s.size()-1; i++){
		if(s[i]!=s[i+1]){
			if(s[i]=='0') cnt_zero++;
			else cnt_one++;
		}
	}
	
	cout<<min(cnt_zero, cnt_one)<<endl;
	
}
    [Oracle SQL]Kataxian結合(Cartesian)
    HIDI Flutter Challenge (9) Container Widget