贪心
- 找最小半径R
- 找连通块,每个连通块都看成只有一个最初感染者, res ++
锻炼了一下自己用pair的熟练度,看来要多用c++的利器
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = 1000010;
PII w[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> w[i].first >> w[i].second; //输入数据
sort(w, w + n); //按照位置排个序,有序状态更好发力。
int R = 0x3f3f3f3f;
for(int i = 0; i < n - 1; i ++) //找到最小的半径,因为是向右看,所以不数最后一头牛
{
if (w[i].second != w[i + 1].second) R = min(R, w[i + 1].first - w[i].first - 1);
} //一直向右看,右侧与当前健康状态不一样,就可以判断是否更新半径
int res = 0; //然后判断连通块数量即可。
for(int i = 0; i < n; i ++) //枚举数连通块
{
if(w[i].second == 1)
{
res ++; //该连通块第一个生病的牛算最初感染者
while(i < n && w[i + 1].first - w[i].first <= R) i ++; //走出这个连通块
}
}
cout << res<< endl;
return 0;
}