今天下午参加了GOOGLE的笔试。被狠虐。
只ac了第一道问题。第二题一开始的思路是把0变成-1，然后算和，得到正负值。这里一来数字变换很麻烦，二来在处理0值情况时考虑有误（其实无需区分，complaint值是一样的），三来forbidden做处理的时候忽略了变换多位可能比变换1位更佳的可能。没有ac。第二题和朋友请教过，总结如下。
写下解题和思考过程。

Problem A. Yogurt

3. 重复2直到遍历完所有的酸奶。

/**
 * @author wuyafang
 * @Title: A
 * @ProjectName Google
 * @Description: TODO
 * @date 18/8/26下午12:55
 */
import java.util.*;
import java.io.*;
public class A {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
//        Scanner in = new Scanner(System.in);
        int t = in.nextInt();  // Scanner has functions to read ints, longs, strings, chars, etc.
        for (int i = 1; i <= t; ++i) {
            int n = in.nextInt();
            int k = in.nextInt();
            int[] Anum = new int[n];
            int result=0;
            for(int j=0;j<n;j++){
                Anum[j]=in.nextInt();
            }
            if(k==n){
                result = n;
            }else {
                Arrays.sort(Anum);
                for(int j=0,count=0;j<n;count++){
                    while(j<n&&Anum[j]<=count){
                        j++;
                    }
                    if(j+k<n){
                        result+=k;
                        j=j+k;
                    }else if(j>=n) {
                        break;
                    }else {
                        result+=n-j;
                        j=n;
                    }
                }
            }
            System.out.println("Case #" + i + ": " + result);
        }
    }
}

Problem B. Milk Tea

注意：
1.一开始在第三步中，想通过每次去替换最优值去得到新的最优选择（做法是选择替换两数组相差值最小的）。感觉可行，但是必须辅助以最佳选择集。有一种特殊情况就是，替换2位比替换一位的抱怨更少。
举例
1
4 4 4
1110
1010
0100
0000
0000
1000
0100
0010

初始的最佳选择可能是0000
但是被禁止了，如果按照先替换1位，再替换两位的思路，我们最后的最佳选择为0001，但是这个选择的complaint数为12；而如果替换2位，变成1010，complaint数只有6。
这就是为什么我们需要每次choice替换时，选择complaint最小的，而且需要再遍历结束后，把这个选择放回到最佳选择集中的原因。而且，由于替换多位和替换1位需要进行complaint数比较，所以我们不能把替换过的choice剔除出最佳选择集中。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author wuyafang
 * @Title: B
 * @ProjectName Google
 * @Description: TODO
 * @date 18/8/26下午2:31
 */
public class B {
    public static void main(String[] args) {
//        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();  // Scanner has functions to read ints, longs, strings, chars, etc.
        for (int i = 1; i <= t; ++i) {
            int n = in.nextInt();
            int m = in.nextInt();
            int p = in.nextInt();
            int[] count0 = new int[p];
            int[] count1= new int[p];
            LinkedList<String> not = new LinkedList<String>();
            for(int j=0;j<n;j++) {
                String temp = in.next();
                for(int y=0;y<p;y++) {
                    if (temp.charAt(y) == '0') {
                        count0[y]++;
                    } else {
                        count1[y]++;
                    }
                }
            }
            for(int j=0;j<m;j++) {
                String temp = in.next();
                not.add(String.valueOf(temp));
            }

            StringBuilder res = new StringBuilder();
            //找到理想的
            for(int j=0;j<p;j++) {
                if(count0[j]>count1[j]){
                    res.append('0');
                }else{
                    res.append('1');
                }
            }
            String tempString = res.toString();
            HashSet<String> resultSet = new HashSet<String>();
            resultSet.add(tempString);
            while(not.contains(tempString)){
                int min = Integer.MAX_VALUE;
                for(String choice:resultSet){
                    for(int b = 0; b < p; ++b) {
                        StringBuilder sb = new StringBuilder(choice);
                        sb.setCharAt(b,sb.charAt(b)=='1'?'0':'1');
                        String curString = sb.toString();
                        if(resultSet.contains(curString)){
                            continue;
                        }
                        int temp = getComplaint(curString,count0,count1);
                        if(temp<min){
                            min = temp;
                            tempString = curString;
                        }
                    }
                }
                if(not.contains(tempString)){
                    resultSet.add(tempString);
                }else{
                    break;
                }
            }
            int result = getComplaint(tempString,count0,count1);
            System.out.println("Case #" + i + ": " + result);
        }
    }

    private static int getComplaint(String tempString,int[] count0,int[] count1){
        int result =0;
        for(int j=0;j<tempString.length();j++){
            if(tempString.charAt(j)=='1'){
                result+=count0[j];
            }else {
                result+=count1[j];
            }
        }
        return result;
    }
}