题解：P9953 [USACO20OPEN] Social Distancing II B

HsNu1ly7_ · 2024-07-22 18:46:53 · 题解

思路

我们可以通过每头奶牛的染病情况来判定 R 的取值范围，如果奶牛 i 未染病，就可以找到离它最近的染病的奶牛的位置，从而更新 R 。

接着我们继续判断如果两头染病的牛的距离小于 R 那么这两头牛可以互相传染，否则答案加一。

代码如下：

#include <iostream>
#include <algorithm>
using namespace std ;
#define int long long
int n ;
struct node {
    int x , s ;
}arr[1010];

bool cmp ( node a , node b ){ return a.x < b.x ; }

signed main (){
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;
    cin >> n ;
    for ( int i = 1;  i <= n ;i++ ) cin >> arr[i].x >> arr[i].s ;

    sort ( arr + 1 , arr + 1 + n , cmp ) ;

    int R = 0x3f3f3f3f ;

    for ( int i = 1 ; i <= n ;i++ ){
        if ( !arr[i].s ){
            if ( arr[i + 1].s && i < n ){
                R = min ( R , arr[i + 1].x - arr[i].x ) ;
            }
            if ( arr[i - 1].s && i > 0 + 1 ){
                R = min ( R , arr[i].x - arr[i - 1].x ) ;
            }
        }
    }
    int cnt = 0 ;
    for ( int i = 1 ; i  <= n ; i++ ){
        if ( arr[i].s ){
            if ( arr[i - 1].s && arr[i].x - arr[i - 1].x < R ){
                cnt = cnt ;
                swap ( cnt , n ) ;
                swap ( cnt , n ) ;
                arr[i].s = arr[i].s ;
                continue ;
            }
            ++cnt ;
        }
    }
    cout << cnt ;
    return 0 ;
}