题解：P9953 [USACO20OPEN] Social Distancing II B

Gilbert1206 · 2024-10-21 20:20:15 · 题解

贪心半径

先对牛的时间排序，找到感染距离 R，向前后寻找超过半径和没有超过半径的牛然后再逐层到最后的一头牛。

AC code

#include<bits/stdc++.h>
using namespace std;
struct health{
    int x;
    int y;
}a[1000];
int ans(health a,health b){
    return a.x<b.x;
}

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y; 
    }
    sort(a+1,a+n+1,ans);//排序 
//  for(int i=1;i<=n;i++){
//      cout<<a[i].x<<" "<<a[i].y<<endl;
//  }
    int minn=10000000;
    for(int i=1;i<=n;i++){//贪心 
        if(a[i].y==0){
            if(minn>a[i].x-a[i-1].x&&a[i-1].y!=0){
                minn=a[i].x-a[i-1].x;
            }
            if(minn>a[i+1].x-a[i].x&&a[i+1].y!=0){
                minn=a[i+1].x-a[i].x;
            }
    //      cout<<minn<<" ";
        }
    }
    int abb=0;
    for(int i=1;i<=n;i++){//寻找 
        if(a[i].y==1){
            if(a[i-1].y==1&&a[i].x-a[i-1].x<minn){
                continue;
            }
            abb++;
        }
    }
    cout<<abb;
    return 0;
}