SRM 223 Div II Level Two: BlackAndRed，O(N)復雜度

      這道題目最直接最暴力的算法就是遍歷每個位置，然後查看是否滿足條件，滿足條件的話則立刻停止遍歷，   這樣算法的時間復雜度為O(N^2)。不過還有一個更高效的方法，其時間復雜度為O(N)，只需進行一次遍歷   就可以了。該題目的作者給出了最好的解答，如下：     To visualize the O(N) solution, make a graph where the value at position x is the number of black cards in the first x cards, minus the number of red cards in the first x cards. x increases as each new card is turned over, and the graph goes up one unit if it is black, and down one unit if it is red.   Here is graph for the "RBBRRRRBBBRBBRRBRBBRRRRBBBBBRRRB":                                   /\        /\        /\    /\      /  \      \/  \    /\/  \/\/  \    /    \/           \  /            \  /            \/              \/Notice that this graph ends up at the same level at which it starts, because there are an equal number of red and black cards. If the value ever dips below the starting value (as it does in this graph), that means you lose the game. Cutting the deck is equivalent to moving the same number of line segments from the front of the graph to the end. So finding the right place to cut the deck is equivalent to finding the right place to cut the graph such that the value never dips below the starting value. This point is, obviously, at the minimum of the graph. If there are more than one, you select the left-most minimum (corresponding to the cut with the fewest cards.) In this example, that point is seven units from the left, so the answer is 7.     實現該算法的代碼如下：

#include <string>
#include <vector>
using namespace std;

class BlackAndRed {
public:
    int cut(string deck) {
	int res = 0;
	int minpoint = 0;
	int point = 0;
	for (int i = 0; i < deck.size(); i++) {
		if ('R' == deck[i]) {
			--point;
		} else {
			++point;
		}
		if (point < minpoint) {
			minpoint = point;
			res = i + 1;
		}
	}
	return res;
    }
};