无法找到Codechef练习题的解决方案

0 投票

2 回答

615 浏览

提问于 2025-04-15 15:30

这是来自Code Chef的问题：

一组N位重要人物刚刚抵达德里，正在等待交通工具前往鲁尔基，参加Cognizance的开幕仪式。由于他们是Cognizance的大赞助商，组织团队认为不应该让一个车里坐多个重要人物。此外，每位重要人物提前向组织团队说明了他们喜欢的交通方式。因此，组织团队列出了每位重要人物可以接受的交通工具清单。现在，你需要根据这些偏好和德里可用的N辆车，判断是否能安排车辆，让每个人的偏好都能得到满足。每位重要人物最多只能占用一个交通工具。

输入格式：

第1行：N - 重要人物的数量。1 <= N <= 100

第2到N+1行：每位重要人物的名字 - 每行一个名字。

第N+2到2*N+1行：每辆车的名字 - 每行一个名字。

第N+2行开始：K - 每位重要人物的偏好列表大小，后面跟着K个用空格分开的可接受的交通方式名字。K <= N

注意：所有名字的长度都不会超过100。

输出格式：

第1行：是/否。

示例输入：

Divye

Rohit

Akshat

Parth

Scorpio

BMW

Ford

Chevrolet

1 BMW

1 Ford

2 Scorpio Chevrolet

1 Ford

示例输出：

否

问题链接：http://www.codechef.com/problems/INSOMB6/

这是我写的代码：

#!/usr/bin/python

ceo = []
cars = []
error = True
n = int(raw_input())
for i in range(n):
 ceo.append(raw_input().lower())
for i in range(n):
 cars.append(raw_input().lower())

for i in range(n):
 test = raw_input().lower().split()
 if int(test[0]) is not len(test[1:]):
  error = False
  continue
 if test[0] != '0':
  for i in test[1:]:

   try :
    cars.remove(i)
   except ValueError :
    error = False

if error and  len(cars) is 0 :
 print "Yes"
else : 
 print "No"

这段代码对示例输入给出了正确的输出。但在某些情况下它会失败。如果你们能指出这段代码失败的情况，那就太好了！

数据结构算法逻辑推理组合优化代码挑战交通分配偏好匹配车辆调度

2 个回答

考虑这个测试案例：

答案是肯定的，因为A可以使用车2，而B会使用车1。

我觉得你的解决方案会把A放在车1上，然后就无法再放人B了。

如果你想要一些提示，这个问题可以简化为判断一个二分图是否存在完美匹配。

回答于 2025-04-15 由 Python大师

分享举报

首先，有一个错误（我怀疑这可能不是你遇到的主要问题）：

if int(test[0]) is not len(test[1:]):

用 is 或 is not 来测试不可变类型（比如数字）是错误的，应该用 = 或 !=。你写的代码在某些版本的 Python 中可能偶然能工作，因为这些版本会“缓存”小整数，但这依然是错误的;-)。同样，后面用 len(cars) is 0 也是不对的。

用一个叫 error 的变量来表示“没有错误”是有点奇怪和令人困惑的（虽然从技术上讲，这并不是错误的代码;-）。

算法上的问题是：你检查的只是每辆车是否被恰好一个贵族喜欢。这和“是否存在一个一对一的分配，将车和贵族的偏好匹配起来”是完全不同的。例如，如果所有贵族都喜欢所有的车，你会说“不”，因为你在循环的第一轮就把所有车都移除了，第二轮就会出现 ValueError，从而把 error 设置为 False，但显然答案应该是“是的”！所以，重新从头思考这个算法吧。考虑使用集合或字典，它们可能会让你的工作更轻松（虽然不会改变算法，但可能更容易理解和构思）。

回答于 2025-04-15 由 Python大师

分享举报

无法找到Codechef练习题的解决方案

2 个回答

撰写回答