Social distance (cow infection)

Title Description
Due to the highly contagious bovine infectious disease COWVID-19 The outbreak ,Farmer John Very worried about the health of his cows .

Although he did his best to make his N Cows practice “ Social distance ”, There are still many cows unfortunately infected with the disease .

The number is 1…N The cows are located in different positions on a long straight road （ Equivalent to one-dimensional number axis ）, cow i In position xi.

Farmer John Know that there is a radius R, Any cow not more than... Away from an infected cow R Cows in the unit will also be infected （ Then it will spread to the distance R Cows in the unit , And so on ）.

Unfortunately ,Farmer John I don't know for sure R Value .

All he knows is which of his cows are infected .

Given this data , Find out the minimum number of cows initially infected with the disease .

Input format
The first line of input contains N.

following N Use two integers for each line x and s Describe a cow , among x For position ,s by 0 A healthy cow ,1 Indicates an infected cow , And all cows that may be infected by transmission have been infected .

Output format
Output the minimum number of cows that have been sick before the disease begins to spread .

Data range
1≤N≤1000,
0≤x≤106

 Examples 
 sample input ：
6
7 1
1 1
15 1
3 1
10 0
6 1
 sample output ：
3

Ideas ：

（ At first, I didn't think so much , I went to simulate , Discovery is also to find a different state , Some are like double pointers hhh)
Apply y In general, I talked about the ideas of similar topics , First there is a radius R, Any cow not more than... Away from an infected cow R Cows in the unit will also be infected （ Then it will spread to the distance R Cows in the unit , And so on ）.
Roughly divided into several sections , It can be considered that cows in each section will be infected ;
If two intervals contain each other , We can divide two disjoint intervals and replace them ;
If two intervals intersect , Then we can also divide two disjoint intervals ;

Then we can find out that at least one optimal solution satisfies the property of disjoint of each interval ;
All within our scope , The interval can only be covered 1 Time or 0 Time ;

First, find the minimum R —— This enumerates ;

Double pointer template ：（ Note appended ： The time complexity was wrong last time , Should be O(n))

for(int i=0,j=0;i<n;i++)
{
    while(j<i && check(i,j)) j++;
    // The specific logic of each topic 
}

Simple solution ：

for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)

The core of optimization is i and j The law of change —— monotonicity ;
In fact, whether cows are infected , Follow R of ;
We are looking for the sum of the distance between each cow and the cows next to it R The relationship between
If you exceed the distance R It means that you can't get infected , Otherwise, it will cause infection ;
It is equivalent to asking how many infected groups there are , The answer in this question is that at least a few cows are infected , Their results are exactly the same ;
Then we will find out j be relative to i Always forward ;
Thus, double pointers can be used ;

Time complexity O(n)
reference
C++ Code

#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 Code

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);
    }
}

The solution of other big guys ：

Train of thought two ： simulation  

Python Code

Time complexity ：O(n)

def main():
    n = int(input())
    nums = []
    for _ in range(n):
        x, f = map(int, input().split())
        nums.append((x, f))

    nums.sort()

    R = float('inf')
    for i in range(n - 1):
        if nums[i][1] != nums[i + 1][1]:
            R = min(R, nums[i + 1][0] - nums[i][0] - 1)

    res = 0
    i = 0
    while i < n:
        if nums[i][1] == 1:
            res += 1
            while i + 1 < n and nums[i + 1][0] - nums[i][0] <= R:
                i += 1
        i += 1

    print(res)

if __name__ == "__main__":
    main()

Train of thought three ： Two points + Double pointer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define pii pair<int, int>
#define fir first
#define pb push_back
#define sec second
int n;
vector<pii> a;
bool check (int tar) {
    bool f =1;
    for (int i = 1; i <= n; i ++) {
        if (a[i].sec) continue;
        if (i == 1) {
            if (a[i + 1].sec&& a[i + 1].fir - a[i].fir <= tar) return 0;
        }
        else if (i == n ) {
            if (a[i - 1].sec && a[i].fir - a[i - 1].fir <= tar) return 0;
        }
        else {
            if (a[i - 1].sec)
                if (a[i].fir - a[i - 1].fir <= tar) return 0;
            if (a[i + 1].sec)
                if (a[i + 1].fir - a[i].fir <= tar) return 0;
        }
    }
    return 1;
}
void solve() {
    cin >>n;
    a.pb({0, 0});
    for (int i = 0; i< n ;i ++)
        {
            int x, y;
            cin >> x >> y;
            a.pb({x, y});
        }

    sort(a.begin(), a.end());
    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = l + r + 1>> 1;
        if (check(mid))l = mid;
        else r = mid - 1;
    }
    // Two points to find the biggest one that meets the requirements R
    int ans = 0;
    for (int i = 1, j = 2; i <= n;  i++)
    {
        j = i + 1;
        while (j <= n && a[j].fir - a[j - 1].fir <= l) j ++;
        ans++;
        i = j - 1;

    }
    // Double pointer finds the number of groups 
    cout << ans << endl;
}
int main () {
    int t;
    t = 1;
    while (t --) solve();
    return 0;
}
// Two points to find the biggest r. Then scan with double pointer .

Train of thought four ： enumeration + greedy （ The solution of this boss is really nb ,hhh）

#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=1010;
typedef pair<int,int>PII;
PII a[N];
int main()
{
    int n;
    scanf("%d",&n);
    int distance;
    for(int i=0;i<n;i++)
    {
    scanf("%d %d",&a[i].x,&a[i].y);
    }
    sort(a,a+n);// Sort 
    for(int i=0;i<n;i++)         // find R
    {
          if(!a[i].y)
    {
        if(!i&&a[i+1].y)distance=min(distance,a[i+1].x-a[i].x);
        if(i&&a[i-1].y)distance=min(distance,a[i].x-a[i-1].x);
        if(i&&a[i+1].y)distance=min(distance,a[i+1].x-a[i].x);
    }
    }
    int cnt=0;
    for(int i=0;i<n;i++)// Find different sets according to the situation   It can be seen as yesterday's daily question   Find the number of different sub segments 
    {
        if(!i&&a[i].y)cnt++;                // The first is 1
        if(i&&!a[i-1].y&&a[i].y)cnt++;     // The former and now   One for 0  One for 1
        if(i&&a[i-1].y&&a[i].y&&a[i].x-a[i-1].x>=distance)cnt++;
         // The former   And now are 1 But distance >=R
    }
    cout<<cnt;
}

Train of thought five ：map+ enumeration

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;
map<int,int>mp;

int main()
{
    int n,x,y;
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>x>>y;
        mp[x]=y;
    }
    int now=-1,f=-1,len=INT_MAX;
    // First calculate R The minimum value of 
    for(auto& i:mp){
        if(now==-1){
            now=i.first;
            f=i.second;
        }
        else{
            if(i.second!=f){
                len=min(len,i.first-now);
            }
            now=i.first;
            f=i.second;
        }
    }
    int ans=0;
    now=-1;
    for(auto& i:mp){
        if(now==-1){
            now=i.first;
            f=i.second;
            if(f==1)  
                ans++;
        }
        else{
            if(i.second==f&&f==1){
                if(i.first-now>=len) // The distance between two sick cows is greater than or equal to R  ans++
                    ans++;
            }
            else if(i.second!=f&&f==0)  
          // A sick cow meets a sick cow   It means that at least one cow on the other side must be sick   ans++
                ans++;
            now=i.first;
            f=i.second;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Welcome to leave a message like

Ouch, ouch