hihoCoder #1135 : Magic Box

题目地址：http://hihocoder.com/problemset/problem/1135
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
The circus clown Sunny has a magic box. When the circus is performing, Sunny puts some balls into the box one by one. The balls are in three colors: red(R), yellow(Y) and blue(B). Let Cr, Cy, Cb denote the numbers of red, yellow, blue balls in the box. Whenever the differences among Cr, Cy, Cb happen to be x, y, z, all balls in the box vanish. Given x, y, z and the sequence in which Sunny put the balls, you are to find what is the maximum number of balls in the box ever.

For example, let’s assume x=1, y=2, z=3 and the sequence is RRYBRBRYBRY. After Sunny puts the first 7 balls, RRYBRBR, into the box, Cr, Cy, Cb are 4, 1, 2 respectively. The differences are exactly 1, 2, 3. (|Cr-Cy|=3, |Cy-Cb|=1, |Cb-Cr|=2) Then all the 7 balls vanish. Finally there are 4 balls in the box, after Sunny puts the remaining balls. So the box contains 7 balls at most, after Sunny puts the first 7 balls and before they vanish.

输入
Line 1: x y z

Line 2: the sequence consisting of only three characters ‘R’, ‘Y’ and ‘B’.

For 30% data, the length of the sequence is no more than 200.

For 100% data, the length of the sequence is no more than 20,000, 0 <= x, y, z <= 20.

输出
The maximum number of balls in the box ever.

提示
Another Sample

Input

0 0 0
RBYRRBY

Output

4

样例输入

1 2 3
RRYBRBRYBRY

样例输出

7

Java 代码如下：

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in= new Scanner(System.in);
        int[] xyz=new int[3];
        int max=0,cr=0,cy=0,cb=0;
        xyz[0]=in.nextInt();
        xyz[1]=in.nextInt();
        xyz[2]=in.nextInt();
        Arrays.sort(xyz);
        String temp=in.next();
        for(int i=0;i<temp.length();i++){
            switch (temp.charAt(i)) {
                case 'R':cr++;break;
                case 'Y':cy++;break;
                case 'B':cb++;break;
            }
            max=max>(cr+cy+cb)?max:(cr+cy+cb);
            int[] a=new int[3];
            a[0]=Math.abs(cr-cy);
            a[1]=Math.abs(cr-cb);
            a[2]=Math.abs(cy-cb);
            Arrays.sort(a);
            if(a[0]==xyz[0]&&a[1]==xyz[1]&&a[2]==xyz[2]){
                cr=0;
                cy=0;
                cb=0;
            }

        }
        System.out.println(max);
    }

}

思路：Cr,Cy,Cb，三个数共能产生3个差值（绝对值），如果这三个值跟x,y,z分别对应上了，就把三个数清零。把两个数组（差值数组和xyz数组）分别排序，比较对应位置是否相等即可。

遇到了一个问题，就是题中并没有说x,y,z是按照从小到大顺序给出了，忘了排序。