累積和の典型問題
問題概要
WWEWEEWWEE のような文字列が与えられる。
文字列のうちの 1 つの文字を選んで、その左側をすべて E に、右側をすべて W にするのに必要な変更量の最小値を求めよ。
制約
解法
累積和を用いる。
#include <iostream> #include <string> using namespace std; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } int N; string S; int solve() { int allE = 0, allW = 0; for (int i = 0; i < (int)S.size(); ++i) { if (S[i] == 'E') ++allE; else ++allW; } int res = (int)S.size(); int curE = 0, curW = 0; for (int i = 0; i < (int)S.size(); ++i) { int migiE = allE - curE; if (S[i] == 'E') --migiE; chmin(res, curW + migiE); if (S[i] == 'E') ++curE; else ++curW; } return res; } int main() { while (cin >> N >> S) { cout << solve() << endl; } }