HDU 3363 Ice-sugar Gourd （贪心）

题意：给你一个串，串中有H跟T两种字符，然后切任意刀，使得能把H跟T各自分为原来的一半。

析：由于只有两个字母，那么只要可以分成两份，那么一定有一段是连续的。

代码如下：

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <string>

#include <algorithm>

#include <vector>

#include <map>

using namespace std ;

typedef long long LL;

const int maxn = 1e5 + 5;

const int INF = 0x3f3f3f3f;

char s[maxn];

int main(){

    int n, x;

    while(scanf("%d", &n) == 1 && n){

        scanf("%s", s);

        int h = 0, t = 0;

        for(int i = 0; i < n; ++i){

            if(s[i] == 'H') ++h;

            else ++t;

        }

        if((t&1) || (h&1)){

            printf("-1\n");

            continue;

        }

        t /= 2;

        h /= 2;

        int ss = 0, e = 0;

        int cnth = 0, cntt = 0;

        while(ss < n){

            bool ok = false;

            while(e < n && cnth + cntt < n/2){

                s[e] == 'H' ? ++cnth : ++cntt;

                ++e;

                if(cnth == h && cntt == t){

                    ok = true;

                    if(ss == 0)  printf("1\n");

                    else  printf("2\n");

                    if(ss == 0)  printf("%d\n", n/2);

                    else  printf("%d %d\n", ss, ss+n/2);

                }

            }

            if(ok) break;

            s[ss] == 'H' ? --cnth : --cntt;

            ++ss;

        }

    }

    return 0;

}