算法训练——GCJ-2008-R1A-B-Milkshakes

题目链接: https://code.google.com/codejam/contest/32016/dashboard#s=p1

分析:

注意到每个customer最多只能有一种奶昔是”malted”的,这点是解决这题的关键。可以推出以下结论:

  1. 如果所有用户至少有两种喜欢的奶昔,那么必然有一种是”unmalted”,那只要保证所有奶昔种类都是”malted”就解决了。
  2. 如果有部分用户只喜欢一种奶昔,如果该奶昔是”unmalted”的,那么可以不用管它。
  3. 如果有用户喜欢一种奶昔,且”malted”,那么需要处理
算法描述:

针对分析,我们处理第三点,逻辑流程如下:

  1. 为了满足那部分用户,相应的奶昔我们只能做成”malted”
  2. 遍历所有customer:
  3. 如果他们没有对于已经”malted”奶昔的偏好,跳过
  4. 如果他们的偏好中也喜欢某一种”malted”奶昔,那么这个用户的偏好已经得到满足,可以从customer列表中剔除
  5. 如果他们偏好中不喜欢该”malted”奶昔,把相应的奶昔从那些customer的偏好列表中删除,尝试用其它的奶昔去满足他们的需求
  6. 处理的过程中如果发现某一个用户的偏好已经为空了,表示他的需求无法满足,直接返回”IMPOSSIBLE”
  7. 逻辑流程走到这里,表示必须做成”malted”的奶昔已经处理完毕,后续的逻辑可以不用考虑这种奶昔的存在,重新回到 1 循环。

主循环体退出的条件:客户列表为空或者已经不存在只偏好某一种”malted”奶昔的客户

备注: 因为每次循环都会减少总体奶昔的数量,所以上次还存在多种偏好的customer到了下次循环的时候偏好就有可能只剩一种了,这个是动态变化的。

代码:

写得稀碎的python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
with open("B-large-practice.in") as f:
C = int(f.readline())
for i in range(C):
N = int(f.readline())
M = int(f.readline())
l = []
for j in range(M):
tmp = {}
line = f.readline().strip().split()
for k in range(int(line[0])):
tmp[int(line[2 * k + 1])] = int(line[2 * k + 2])
l.append(tmp)
ans = {}
# solution logic insert below
possible = True
while len(l) and possible:
new_malted = None
for c in l:
if len(c) > 1:
continue
if c[c.keys()[0]] == 1:
ans[c.keys()[0]] = 1
new_malted = c.keys()[0]
break
elif c.keys()[0] in ans:
possible = False
break
if new_malted is None:
break

del_list = []
for c in l:
if new_malted in c:
if c[new_malted]:
del_list.append(c)
continue
else:
del c[new_malted]
if len(c) == 0:
possible = False
break
for c in del_list:
l.remove(c)

# output result
res = "Case #{0}:".format(i + 1)
if not possible:
res += " IMPOSSIBLE"
else:
for i in range(N):
if i + 1 in ans:
res += " 1"
else:
res += " 0"
print res