今天下午参加了GOOGLE的笔试。被狠虐。
只ac了第一道问题。第二题一开始的思路是把0变成-1，然后算和，得到正负值。这里一来数字变换很麻烦，二来在处理0值情况时考虑有误（其实无需区分，complaint值是一样的），三来forbidden做处理的时候忽略了变换多位可能比变换1位更佳的可能。没有ac。第二题和朋友请教过，总结如下。
写下解题和思考过程。
Problem A. Yogurt
https://code.google.com/codejam/contest/4394486/dashboard#s=p0
主要思路：
1.先排序
2.排序完，看当前位置的过期时间和当天天数对比。如果过期时间大于天数，说明接下来的k个酸奶都没过期，直接遍历k个（如果剩余不足k则数量为剩余数目），进入下一个天数判断；如果过期时间小于等于天数，说明当前的酸奶已过期，一直向后寻找到过期时间大于天数的，在此位置开始直接遍历k个（如果剩余不足k则数量为剩余数目）。
- 重复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
https://code.google.com/codejam/contest/4394486/dashboard#s=p1
思路：
1.用两个数组来分别表示每个位置选择1的和选择0的各自数量；这样算抱怨数的时候就可以直接计算。
2.最佳的选择是每个位置中，数目最多的那个。
3.算forbidden的时候是一个难点。这里采取穷举的方式，列一个最佳选择集。对选择集中的每一个选择，逐位替换，计算complaint。找到最小的complaint，如果不在forbidden里，说明这个选择就是最佳的；否则，把这个选择放到最佳选择集里，重复3的步骤。直到找到一个最佳选择（即不在forbidden里面的选择）
4.计算最佳选择的complaint。抱怨数即，每个位置，和最佳选择不一样的选择人数之和。
注意：
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;
}
}
