自动搬运

查看原文

来自洛谷，原作者为

	Gilbert1206 班尼特厨||xf20280303||原神UID:331504998||CSP-S 冲 220+ || CSP-J AK||互关：/paste/cxk74r5i

搬运于2025-08-24 22:53:20，当前版本为作者最后更新于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;
}