Codejam之Bathroom Stalls

本文主要是介绍Codejam之Bathroom Stalls，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

一间bathroom有N+2个位置，排列在一行。最左边和最右边的位置总是被bathroom guards所占，其他N个可以使用。

当一个人进入，他总是选择距离其他人尽可能远的位置，规则如下：对每一个空位置s，计算Ls和Rs，Ls是s和左边最近的被占位置之间有多少个空位置，Rs是s和右边最近的被占位置之间有多少个空位置。然后从中选择min(Ls,Rs)最大的那些s。如果选到的s只有一个，那最终选择它。否则，再选择max(Ls，Rs)最大的s。如果仍然有多个这样的s，选择最左边的。

K个人依次进入，每个人在下一个人进入之前选择他们的位置。没有人离开。

问题有2个小数据集和1个大数据集。第一个小数据集中的N在[1,1000]，第二个小数据集的N在[1, 10的六次方]，大数据集的N在[1,10的18次方]

输入：第一行是T，测试用例的个数。后面有T行，每行是N K，N是位置的个数，K是人数。
输出：Case #x: y z
x是测试用例的编号
y是最后进入的那个人选择的s的max(Ls,Rs)
z是最后进入的那个人选择的s的min(Ls,Rs)

这里写图片描述

问题解决

思路1

对于第一个小数据集，N的大小在1到1000之间，因此可以简单的模仿规则的执行。

用一个数组来代表所有的位置，1表示该位置已被占，0表示是空位置。每个人进入时扫描整个数组，找到最左的最长连续0的子序列（因为可能有多个连续0的子序列都是最长的），选择子序列中间的那个位置置为1。循环K次模仿K个人进入的场景。

时间复杂度为O(NK)：循环K次，每次要扫描整个数组，数组长度为N+2

int[] states = new int[N+2];
for(int i = 1;i < N + 1;i++){states[i] = 0;
}
states[0] = states[N+1] = 1;
int lo = 0;
int hi = states.length - 1;
for(int i = 1;i <= people;i++){int pos = lo + (hi-lo)/2;if(i == people){//如果是最后一个人的话，计算结果并写入输出文件res1 = (hi-lo-1)/2;  //max(Ls,Rs)res2 = ((hi-lo-1)%2==0)?(res1-1):(res1);  //min(Ls,Rs)break;}states[pos] = 1;   //将这个人选择的位置置为1int[] res = findlongestzeros(states); //找到最长0子串lo = res[0];  //最长0子串的左边位置的索引hi = res[1];  //最长0子串的右边位置的索引
}

思路2

用思路1的方法是无法解决小数据集2的，小数据集2的N在1到10的六次方之间。

事实上我们不需要记录每个位置是0还是1，只需要记录当前的0子串都有哪些长度。用一个集合来记录当前所有0子串的长度，用一个Map来记录一种长度的0子串有多少个。一个人进入时，从集合中找到最大值，也就是最长的那个子串，然后劈成两半（长度为奇数和偶数两种情况），然后更新Map。

int N = Integer.parseInt(aline.split(" ")[0]);
int people = Integer.parseInt(aline.split(" ")[1]);
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(N);   //初始状态N个位置都是空的，最长0子串长度为N
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
map.put(N, 1);   //初始状态长度为N的0子串有1个for(int j=1;j<=people;j++){int maxlen=set.last();  //从集合中选出最大值//这个人选中了最大长度的0子串，从中间选择一个位置，因此得到两个新的0子串int llen=maxlen/2;int rlen=(maxlen%2==0)?(llen-1):llen;if(j==people){writer.write("Case #"+k+": "+llen+" "+rlen+'\n');}//这个长度的0子串已经被分割了，所以个数减一             int newcount = map.get(maxlen)-1;if(newcount==0){set.remove(maxlen);map.remove(maxlen);}else{map.put(maxlen, newcount);}if(llen>0){if(map.containsKey(llen)){map.put(llen, map.get(llen)+1);}else{//如果这个长度是之前没有出现过的map.put(llen, 1);set.add(llen);}}if(rlen>0){if(map.containsKey(rlen)){map.put(rlen, map.get(rlen)+1);}else{map.put(rlen, 1);set.add(rlen);}}
}

K次循环，但是每次循环不需要遍历N+2长度的数组，只需要查找最大值插入移除最大值等，这些操作的复杂度是可以降到logK的。

思路3

不需要循环K次，假设现在最长0子串的长度为8，长度为8的0子串有2个，一个人进来选择一个长度为8的子串，选择中间位置，得到一个长度为3的0子串和一个长度为4的0子串，都比8小，所以下一个人进来势必选择的还是长度为8的0子串。所以我们每次不是选择最长的0子串只选一个，而是全部选中。

大数据集中的几个测试用例如下，已经超出了int的值范围，需要把之前的int改为long

500000000000000000 128
490647352522905448 483027390212853846
366633848859111292 326278824739890730
999999999999999999 288230376151711743
287722564158777742 249250986600580845
820269355774935802 721103772257795482

TreeSet<Long> set = new TreeSet<Long>();
set.add(N);
Map<Long,Long> map = new HashMap<Long,Long>();
map.put(N, (long) (1));
long j=0;
while(true){long maxlen=0;maxlen=set.last();long maxlen_counts=map.get(maxlen);long llen=maxlen/2;long rlen=(maxlen%2==0)?(llen-1):llen;j = j+maxlen_counts;if(j>=people){writer.write("Case #"+k+": "+llen+" "+rlen+'\n');break;}set.remove(maxlen);if(llen>=0){if(map.containsKey(llen)){map.put(llen, map.get(llen)+maxlen_counts);}else{map.put(llen, maxlen_counts);set.add(llen);}}if(rlen>=0){if(map.containsKey(rlen)){map.put(rlen, map.get(rlen)+maxlen_counts);}else{map.put(rlen, maxlen_counts);set.add(rlen);}}
}