1

我刚刚使用 Python 完成了一个关于 Dcoder（“热爱数学”）的挑战。我失败了两个测试用例，但做对了一个。我使用了一些较低级别的 Python，因为我还没有探索更多，所以如果它看起来有点太基础了，我很抱歉。挑战内容如下：

Dcoder 学校的学生热爱数学。他们喜欢阅读各种数学书籍。为了确保他们保持快乐，他们的数学老师决定为他们买更多的书。如果班里至少有 X 本书而不超过 Y 本书，学生会很高兴，因为他们知道“只工作不玩耍会使杰克成为一个无趣的男孩”。老师想买最少数量的书来制作最大数量的学生快乐。

输入

输入的第一行包含一个整数 N，表示班级中的学生人数。接下来是 N 行，每行分别包含两个整数 X 和 Y。

#Sample Input
5
3 6
1 6
7 11
2 15
5 8

输出

输出两个以空格分隔的整数，表示所需的最少数学书籍数量和最多快乐学生的数量。

解释：老师可以买 5 本书，让学生 1、2、4 和 5 开心。

#Sample Output
5 4

约束：1 <= N <= 10000 1 <= X, Y <= 10^9

我的代码：

n = int(input())
l = []
mi = []
ma = []
for i in range(n):
  x, y = input().split()
  mi.append(int(x))
  ma.append(int(y))
  if i == 0:
    h=ma[0]
  else:
    if ma[i]>h:
      h=ma[i]

for i in range(h):
  c = 0
  for j in range(len(mi)):
    if ma[j]>=i and mi[j]<=i:
      c+=1
  l.append(c)
great = max(l)
for i in range(1,len(l)+1):
  if l[i]==great:
    print(i,l[i])
    break

我的方法： 我首先将两个最小值和最大值变量分配给两个不同的列表——一个包含最小值，另一个包含最大值。然后我创建了一个循环，处理从 0 到包含最大值的列表的最大可能值的所有数字，并增加每个数字的计数。每次在学生的有利范围内时加 1。在这种特定情况下，我得到的计数列表是（对于上面给定的输入）： [1,2,3,3,4,4,3,3,2 ...]等等。所以我可以最终确定 4 将是最大数量。学生，并且列表中的第一个索引 4 将是最小的没有。所需的教科书。但只有 1 个测试用例有效，两个失败。如果有人可以在这里帮助我，我将不胜感激。谢谢你。

4

2 回答 2

4

这个问题类似于最小平台问题。

在那，您需要分别按升序对最小和最大数学书籍数组进行排序。尝试从上面的链接（平台问题）中理解问题，那么这将是小菜一碟。

这是您的解决方案：

n = int(input())
min_books = []
max_books = []
for i in range(n):
  x, y = input().split()
  min_books.append(int(x))
  max_books.append(int(y))

min_books.sort()
max_books.sort()

happy_st_result = 1
happy_st = 1
books_needed = min_books[0]

i = 1
j = 0
while (i < n and j < n): 
  if (min_books[i] <= max_books[j]): 
    happy_st+= 1
    i+= 1

  elif (min_books[i] > max_books[j]): 
    happy_st-= 1
    j+= 1

  if happy_st > happy_st_result:
    happy_st_result = happy_st
    books_needed = min_books[i-1]

print(books_needed, happy_st_result)

试试这个，如果您需要任何澄清，请告诉我。

于 2020-06-13T14:23:49.227 回答
2

@Vinay Gupta 的逻辑和解释是正确的。如果您按照这些思路进行思考，那么您应该立即清楚答案。

我在下面的代码中实现了相同的逻辑，除了使用更少的行和很酷的内置 python 函数。

# python 3.7.1
import itertools

d = {}
for _ in range(int(input())):
    x, y = map(int, input().strip().split())

    d.setdefault(x, [0, 0])[0] += 1
    d.setdefault(y, [0, 0])[1] += 1

a = list(sorted(d.items(), key=lambda x: x[0]))
vals = list(itertools.accumulate(list(map(lambda x: x[1][0] - x[1][1], a))))

print(a[vals.index(max(vals))][0], max(vals))

上面的答案也被 Dcoder 接受了。

于 2020-06-13T14:53:50.780 回答