题目描述
由于高传染性的牛传染病 COWVID-19 的爆发,Farmer John 非常担忧他的奶牛们的健康。
尽管他尽了最大努力使他的 N 头奶牛们践行“社交距离”,还是有许多奶牛不幸染上了疾病。
编号为 1…N 的奶牛们分别位于一条长直道路上的不同位置(相当于一维数轴),奶牛 i 位于位置 xi。
Farmer John 知道存在一个半径 R,任何与一头被感染的奶牛距离不超过 R 单位的奶牛也会被感染(然后会传染给与其距离 R 单位内的奶牛,以此类推)。
不幸的是,Farmer John 并不确切知道 R 的值。
他只知道他的哪些奶牛被感染了。
给定这个数据,求出起初感染疾病的奶牛的最小数量。
输入格式
输入的第一行包含 N。
以下 N 行每行用两个整数 x 和 s 描述一头奶牛,其中 x 为位置,s 为 0 表示健康的奶牛,1 表示染病的奶牛,并且所有可能因传播而染病的奶牛均已染病。
输出格式
输出在疾病开始传播之前已经得病的奶牛的最小数量。
数据范围
1≤N≤1000,
0≤x≤106
样例
输入样例:
6
7 1
1 1
15 1
3 1
10 0
6 1
输出样例:
3
算法1
双指针算法 $O(nlogn)$
(刚开始我也没想那么多,就去模拟了一下,发现同样是找下一个不同的状态,有的像双指针hhh)
运用下y总之前讲类似题目的思路,首先存在一个半径 R,任何与一头被感染的奶牛距离不超过 R 单位的奶牛也会被感染(然后会传染给与其距离 R 单位内的奶牛,以此类推)。
大致分成几段区间,可以认为每段区间内的奶牛会被感染;
如果俩个区间相互包含,我们可以分出俩段不相交的的区间以之代替;
如果俩个区间相交,那我们也可以分出俩段不相交的区间;
那么我们可以找出至少一个最优解是满足每段区间不相交的性质;
所有在我们的所有范围内,区间只可能被覆盖1次或0次;
首先先求出最小的R ——这个枚举一下;
双指针模板:
for(int i=0,j=0;i<n;i++)
{
while(j<i && check(i,j)) j++;
//每道题目的具体逻辑
}
朴素解法:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
优化核心在于i和j的变化规律——单调性;
其实奶牛是否感染,跟R有关;
我们关注的是在寻找每头奶牛与旁边奶牛距离之差和R的关系
如果超出距离R说明感染不到,否则引起感染;
相当于求感染群体有几个,本题中求得是至少几头牛感染,它们的结果正好是相同的;
那么我们会发现j相对于i始终是向前的;
由此可以用双指针;
感谢@椒盐土豆 提出的错误hhh
时间复杂度 O(nlogn)
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10;
int n,ans;
vector<PII>s;
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ )
{
int x,y;
cin>>x>>y;
s.push_back({x,y});
}
sort(s.begin(),s.end());
int r_min=1e7;
int t=s[0].y;
for (int i = 1; i < n; i ++ )
{
if(t!=s[i].y) r_min=min(r_min,s[i].x-s[i-1].x-1);
t=s[i].y;
}
for (int i = 0; i < n; i ++ )
{
if(s[i].y)
{
ans++;
int j=i+1;
while(j<n&&s[j].x-s[j-1].x<=r_min)j++;
i=j-1;
}
}
return cout<<ans,0;
}
Java代码
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Node
{
int x;
int f;
Node(int x, int f)
{
this.x=x;
this.f=f;
}
}
public class Main
{
public static void main(String [] args)
{
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
List<Node> nums = new ArrayList<>();
for (int i = 0; i < n; i ++)
{
int x = cin.nextInt();
int f = cin.nextInt();
nums.add(new Node(x, f));
}
Collections.sort(nums, (o1, o2) -> o1.x - o2.x);
int R = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; i ++)
{
if (nums.get(i).f != nums.get(i + 1).f)
{
R = Math.min(R, nums.get(i + 1).x - nums.get(i).x - 1);
}
}
int ans = 0;
for(int i=0;i<n;i++)
{
if (nums.get(i).f == 1)
{
ans ++;
int j=i+1;
while (j < n && nums.get(j).x - nums.get(j-1).x <= R)j++;
i=j-1;
}
}
System.out.println(ans);
}
}
感觉时间复杂度应该是O(nlogn)吧,i 后面没有回头
我觉得理论上应该是 O(n)的,循环里面的是个常量