首页 > ACM题库 > HDU-杭电 > hdu 3819-a and b problem-数论-[解题报告]hoj
2015
04-13

hdu 3819-a and b problem-数论-[解题报告]hoj

                                          A and B Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 613 Accepted Submission(s): 190

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
 
我的想法是先统计‘A’字符的个数sum.然后在sum长度区间找到最多的一段使'A',个数最多,那么剩下的sum-max即为要移动的字符的个数。
用ct[]统计每个位置到第一个位置上'A'的个数。
然后计算A的个数即可。
代码:
#include<iostream>
#include<cmath>   
#include<string>
using namespace std;
char s[110000];
int ct[110000];
int main()
{
    int t,i,sum,len,j,max,move;
    scanf("%d",&t);
    //getchar();
    for(i=1;i<=t;i++)
    {
      scanf("%s",&s);
      //getchar();
      len=strlen(s);
      memset(ct,0,sizeof(ct));
      sum=0;
      for(j=0;j<len;j++)
      {
        if(s[j]=='A'){sum++;}
        ct[j]=sum;
      }
       max=ct[sum-1];
       for(j=0;j+sum<=len;j++)
        {
            move=ct[j+sum-1]-ct[j-1];
            if (move>max)
                max=move;
        }
        for(;j<len;j++)
        {
            move=ct[(j+sum)%len-1]+ct[len-1]-ct[j-1];
            if (move>max)
                max=move;
        }
        printf("Case %d: %d\n",i,sum-max);
    }
     return 0;
}



版权声明:本文为博主原创文章,未经博主允许不得转载。


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }