Codeforces Round #307 (Div. 2) B. ZgukistringZ

原题: http://codeforces.com/contest/551/problem/B

---

题目大意: 给3个string,a,b,c. 问用a的字母通过交换,最多可以得到多少个b或者c?

---

分析: 本来感觉是dp的题, 后来想想不用那么复杂, 先用三个26个字符数组, 存下三个字符串的字频, 然后用三个变量,num, nums_a, nums_b存下对应a,b,c的个数. 然后暴力破解就可以, 因为题目是求最多b或者c. 我们假设从0个b开始,一步步递增. 看看最多能有多少个. 这里需要注意的是, b的取值应该是从[0,count_b[j]*i > count_a[j]](0个b, 到i个b的第j个字母超过了i个a的第j个字母). 最后输出的时候, 先输出b,再是c, 最后把a剩下的字符输出就行了

 public void solve(int testNumber, InputReader in, OutputWriter out) {
        String a = in.readString();
        String b = in.readString();
        String c = in.readString();
        int[] ca = new int[26];
        int nums = 0;
        int nums_b = 0;
        int nums_c = 0;
        for (int i = 0; i < a.length(); i++) {
            ca[a.charAt(i) -'a']++;
        }
        int[] cb = new int[26];
        for (int i = 0; i < b.length(); i++) {
            cb[b.charAt(i) - 'a']++;
        }
        int[] cc = new int[26];
        for (int i = 0; i < c.length(); i++) {
            cc[c.charAt(i) - 'a']++;
        }
        for (int i = 0; ; i++) {
            boolean flag = true;
            for (int j = 0; j < 26; j++) {
                if (cb[j]*i > ca[j]){
                    flag = false;
                    break;
                }
            }
            if (!flag)
                break;
            int temp = Integer.MAX_VALUE;
            for (int j = 0; j < 26; j++) {
                if (cc[j] == 0)
                    continue;
                temp = Math.min(temp, (ca[j] - cb[j] * i) / cc[j]);
            }
            if (temp + i > nums){
                nums = temp + i;
                nums_b = i;
                nums_c = temp;
            }
        }
        for (int i = 0; i < nums_b; i++) {
            out.print(b);
        }
        for (int i = 0; i < nums_c; i++) {
            out.print(c);
        }
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < ca[i] - cb[i]*nums_b-cc[i]*nums_c; j++) {
                out.print((char)('a'+i));
            }
        }

    }