摘要
Title: 1824. 钻石收藏家
Tag: 双指针、桶排
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1824. 钻石收藏家

• 题意

  奶牛贝茜非常喜欢闪闪发光的东西，她会在业余时间开采钻石。
  她收藏了 N 颗大小不等的钻石，她想将其中的一些摆放在牛棚的展示柜当中。
  为了使展示柜中的钻石尺寸大小相似，她不会将两颗尺寸大小相差超过 K 的钻石同时放在柜子中（刚好相差 K，则没有问题）。
  给定 K，请帮助贝茜计算在展示柜中最多可以摆放多少颗钻石。

• 思路

  • 桶排
    用哈希表记录每个大小的数量，从最小值遍历到最大值，期间统计能放的最大数量
  • 双指针
    排序，排完序后维护一个相差小于k的队列即可

• 代码

  桶排

  '''
  Author: NEFU AB-IN
  Date: 2022-04-12 16:51:34
  FilePath: \ACM\Acwing\1824.py
  LastEditTime: 2022-04-12 16:51:35
  '''
  from collections import Counter
  
  d = Counter()
  INF = 10010
  n, k = map(int, input().split())
  
  mn, mx = INF, -INF
  for i in range(n):
      x = int(input())
      d[x] += 1
      mn = min(mn, x)
      mx = max(mx, x)
  
  ans, cnt = 1, 0
  for i in range(mn, mx + 1):
      cnt += d[i]
      cnt -= d[i - k - 1]
      ans = max(ans, cnt)
  
  print(ans)

  ---

  双指针

  '''
  Author: NEFU AB-IN
  Date: 2022-04-12 16:58:16
  FilePath: \ACM\Acwing\1824.1.py
  LastEditTime: 2022-04-12 17:03:28
  '''
  a = []
  n, k = map(int, input().split())
  for i in range(n):
      a.append(int(input()))
  
  a.sort()
  
  ans = 0
  j = 0
  for i in range(n):
      while j < n and a[i] - a[j] > k:
          j += 1
      ans = max(ans, i - j + 1)
  
  print(ans)