PYTHON

Question

我刚刚使用 Python 在 Dcoder ("Love for Mathematics") 上完成了一项挑战。我没有通过两个测试用例，但答对了一个。我使用了一些较低级别的 Python 因为我还没有探索更多，所以如果它看起来有点太抱歉我很抱歉 basic.The 挑战阅读：

Dcoder学校的学生都热爱数学。他们喜欢阅读各种数学书籍。为了确保他们保持快乐，他们的数学老师决定为他们买更多的书。如果 class 中至少有 X 本书数学书并且不超过 Y 本书，学生会很高兴，因为他们知道 "All work and no play makes Jack a dull boy"。老师想买最少数量的书来赚取最大数量学生快乐。

输入

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

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

输出

输出两个 space 分隔的整数，表示所需的数学书籍的最小数量和快乐学生的最大数量。

解释：老师可以买 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 个测试用例有效，两个失败。如果有人能帮助我，我将不胜感激。谢谢。

Answer 1

这个问题很相似minimum platform problem。

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

这是您的解决方案：

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)

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

Answer 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接受了。

PYTHON - "Love for Mathematics"

PYTHON - "Love for Mathematics"

challenge-response

testcase

python-3.x