摘要
Title: 1660. 社交距离 II
Tag: 二分、贪心、双指针
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1660. 社交距离 II

• 题意

  由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。
  尽管他尽了最大努力使他的 N 头奶牛们践行“社交距离”，还是有许多奶牛不幸染上了疾病。
  编号为 1…N 的奶牛们分别位于一条长直道路上的不同位置（相当于一维数轴），奶牛 i 位于位置 xi。
  Farmer John 知道存在一个半径 R，任何与一头被感染的奶牛距离不超过 R 单位的奶牛也会被感染（然后会传染给与其距离 R 单位内的奶牛，以此类推）。
  不幸的是，Farmer John 并不确切知道 R 的值。
  他只知道他的哪些奶牛被感染了。
  给定这个数据，求出起初感染疾病的奶牛的最小数量。

• 思路

  具体思路

  • 先把0和1的分开，并且进行排序
  • 遍历0的元素，并在1中二分找这个0是在哪两个1中间（为了防止有的0是在开端和结尾，就给开端和结尾加上无穷），这样就可以求出最小的R
  • 之后双指针遍历1列表，根据R看哪几个是同类
  • 复杂度总共$O(nlogn)$

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-02-16 09:44:56
  FilePath: \ACM\Acwing\1660.py
  LastEditTime: 2022-02-16 10:38:22
  '''
  from bisect import bisect_left
  
  INF = int(2e9)
  a = []  #装1
  b = []  #装0
  
  if __name__ == "__main__":
      n = int(input())
      for i in range(n):
          x, op = map(int, input().split())
          if op == 1:
              a.append(x)
          else:
              b.append(x)
  
      a.sort()
      b.sort()
      dis = INF
      a = [-INF, *a, INF]
      for i in range(len(b)):
          id = bisect_left(a, b[i]) - 1
          dis = min(dis, min(a[id + 1] - b[i], b[i] - a[id]))
      res = 0
      i, j = 1, 1
      n = len(a) - 1
      while i < n and j + 1 < n:
          j = i + 1
          while j < n and a[j] - a[i] < dis:
              j += 1
              i += 1
          res += 1
          i += 1
  
      if a[n - 1] - a[n - 2] >= dis:
          res += 1
      print(res)