Hdu3363 贪心

灰太狼 2022-08-03 16:54 142阅读 0赞

题意：给一个字符串只由”H”和”T”组成，可以在字符之间做切割，问是否可以在切割之后将T和H分别平分成两份。若能，输出需要切割的刀数以及分别在第几个字符处做切割；若不能，输出-1.

这道题目比较不好想，但要是想出来了就比较简单了。一开始没什么思路，觉得怎样都不容易写，后来看了大神的分析才恍然大悟。

只要能想明白这道题目最多字需要切两刀，就基本上可以解出来了。

证明如下：若可以的话，将字符的第一个和最后一个接起来，组成一个圆。过圆心将圆平均分成两份，总有一个分法可以满足题意。如其中一份中的H占总字符串中H的一半，组T一定也占一半，故只分析其中的H。假设其中H的数目为n，过圆心切一刀之后，其中一边H的个数为x，另一边H的个数为n-x，有n-x。

#include <iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    int main()
    {
        int n,h,t,a,b,h1,t1;
        char str[100001];
        while(cin>>n&&n){
            h=t=0;
            cin>>str;
            for(int i = 0 ; i < n ; i++){
                if(str[i]=='H')h++;
                if(str[i]=='T') t++;
            }
            if(t%2||h%2)cout<<-1<<endl; 
            //t和h都为偶数时可以满足
            else{
                a=b=t1=h1=0;
                for(int i = 0 ; i < n/2 ; i++){
                    if(str[i]=='H')h1++;
                    else t1++;
                }
                if(h1==h/2&&t1==t/2){
                    cout<<1<<endl<<n/2<<endl;
                    continue;
                }
                int front=0;
                for(int i = n/2 ; i < n ; i++){
                    if(str[i]=='H')h1++;
                    else t1++;
                    if(str[front++]=='H')h1--;
                    else t1--;
                    if(h1==h/2&&t1==t/2){
                        cout<<2<<endl<<front<<" "<<i+1<<endl;
                        break;
                    }
                }
            }
        }
        return 0;
    }