HDU3363Ice-sugarGourd（滑动窗口）

题意：一串冰糖葫芦，由H和T组成，你的任务是将H和T均分，求最少切的刀数以及切的位置

思考一下，特殊情况下两边均分可以中间一刀切好，如果不能一刀均分的话，最多是两刀，而且两个位置相隔一定是n/2

我的思路是先将不可能完成的串和一刀切好的情况判断出来，从左向右统计到当前位置分别有多少个H和T出现过，然后再用滑动方法求出需要切的位置，滑动窗口设为l，r相隔为n/2

代码如下

#include
#include
#include
#include
using namespace std;
const int maxn=100000+5;
char a[maxn];
int h[maxn],t[maxn];
int nh,nt,f1,f2,l,x;
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        nh=nt=f1=f2=0;
        memset(h,0,sizeof(h));
        memset(t,0,sizeof(t));
        getchar();
        scanf("%s",a+1);
        if(n%2!=0) {printf("-1\n");continue;}
        for(int i=1;i<=n;i++)
        {
            if(a[i]=='H') {h[i]+=1;nh++;}
            if(a[i]=='T') {t[i]+=1;nt++;}
            h[i]+=h[i-1];
            t[i]+=t[i-1];
        }
        if(nh==0||nt==0) {printf("1\n%d\n",n/2);continue;}
        if(nh%2==1||nt%2==1) {printf("-1\n");continue;}
        if(h[n/2]==nh/2&&t[n/2]==nt/2) {printf("1\n%d\n",n/2);continue;}
        int l=1,r=n/2;
        while(r<=n)
        {
            if(h[r]-h[l-1]==nh/2&&t[r]-t[l-1]==nt/2) {printf("2\n%d %d\n",l-1,r);break;}
            l++;
            r++;
        }
    }
}