HDU 3819 A and B Problem

A and B Problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 786    Accepted Submission(s): 251

Problem Description After calculating A + B, let’s consider another easy problem which only contains A and B.

You are given a string s containing only the letters 'A' and 'B'. The letters are arranged in a circle, so the last and first characters are adjacent. You will perform a series of swaps until all the 'A's form one consecutive sequence and all the 'B's form another consecutive sequence. In each swap, you can select any two characters and swap them. Find the minimal number of swaps necessary to reach your goal.  

Input The first line contains a single integer T, indicating the number of test cases.

Each test case only contains a string as description.

Technical Specification

1. 1 <= T <= 100

2. 1 <= |S| <= 100000, |S| indicating the length of the string.  

Output For each test case, output the case number first, then the minimal number of swaps.  

Sample Input

3
AABB
ABAB
AABABA
        

Sample Output

Case 1: 0
Case 2: 1
Case 3: 1
        

Author [email protected]  

Source The 6th Central China Invitational Programming Contest and 9th Wuhan University Programming Contest Final  可以用循環數組也可以直接擴充成兩倍計算。隻需要選擇一個範圍，我們讓這個範圍大小是A的個數，一格一格的移動過去，判斷所有情況中這個範圍内B的個數最少是多少，這個就是需要移動的最少的次數了。

#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
string s,t;
int main(){
	int n;
	scanf("%d",&n);
	int zl = 1;
	while(n--)
	{		
		cin >> s;
		int cnta = 0;
		int cnt = 0;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == 'A') cnta++;
		}
		t = s + s;
		for (int i = 0; i < cnta; i++)
		{
			if (t[i] == 'B') cnt++;
		}
		int end = cnta -1;
		int min_cnt = cnt;
		for (int i = 1; i < s.size(); i++)
		{
			if (t[i - 1] == 'B') cnt--;
			if (t[end + 1] == 'B') cnt++;
			end++;
			min_cnt = min(cnt,min_cnt);
		}
		printf("Case %d: %d\n",zl++,min_cnt);
	}
	return 0;
}