1660. 社交距离 II
II 距离 社交
2023-09-27 14:27:32 时间
Powered by:NEFU AB-IN
文章目录
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看哪几个是同类
-
代码
''' 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)
相关文章
- Leetcode: Remove Duplicates from Sorted List II
- FPGA极易入门教程----工具篇(2)Quartus II 的在线调试工具 In-System Sources and Probes(ISSP)
- leetcode 46-Permutations and 47-Permutations II
- hdu1027 Ignatius and the Princess II (全排列 & STL中的神器)
- 【Leetcode】107. 二叉树的层序遍历 II(中等)
- 《信息物理融合系统(CPS)设计、建模与仿真——基于 Ptolemy II 平台》——2.6 类和继承
- JS leetcode II. 左旋转字符串 题解分析
- Python 面向对象封装案例II
- 多目标遗传算法 ------ NSGA-II (部分源码解析) 拥挤距离计算 crowddist.c
- 简单入门——深度学习笔记(Part II)
- 203、【栈与队列】leetcode ——剑指 Offer II 040. 矩阵中最大的矩形 / 85. 最大矩形:暴力+单调栈(C++/Pyhont版本)
- 洛谷 P2622 关灯问题II
- 【LeetCode】63. Unique Paths II
- leetcode-combination sum and combination sum II
- [LeetCode] 598. Range Addition II 范围相加之二
- [LeetCode] 264. Ugly Number II 丑陋数之二
- 264. Ugly Number II
- leetcode122. Best Time to Buy and Sell Stock II 买卖股票的最佳时机 II(简单)