思路:
设每头奶牛的路线起点为 $a_i$,终点为 $b_i$
将所有线段按照 $a_i$ 的大小进行排序,这部分的时间复杂度为 $O(n log n)$
如果线段i
是符合要求的话就会满足以下条件,即线段左边的终点都小于 $b_i$,右边都大于$b_i$
$\forall j<i, b_j < b_i \Leftrightarrow max(b_1,b_2,…,b_{i-1}) < b_i$,
$\forall k>i, b_k > b_i \Leftrightarrow min(b_{i+1},b_{i + 2},…,b_{k-1}) > b_i$
预处理方式:使用两个数组分别记录前缀最大值和后缀最小值,预处理时间复杂度为$O(n)$
前缀最大值:$S_{max_i} = max(S_{max_{i - 1}}, b_i)$
后缀最小值:$S_{min_i} = min(S_{min_{i + 1}}, b_i)$
正式处理:只需要$b_i$大于前缀数组对应位置的值,小于后缀数组对应的值即可,比较的时候时间复杂度为$O(1)$,比较$n$次
即:$S_{max_{i-1}} < b_i < S_{min_{i + 1}}$
时间复杂度为$O(nlogn)$
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define y second
int main()
{
int n;
cin >> n;
vector<pair<int, int>> p(n + 1);
for(int i = 1; i <= n; i ++ )
{
int a, b;
cin >> a >> b;
p[i] = {a, b};
}
//排序
sort(p.begin() + 1, p.end());
//前缀最大值数组和后缀最小值数组
vector<int> smax(n + 2), smin(n + 2);
smin[n + 1] = 2e9, smax[0] = -2e9;
//更新两个数组
for(int i = 1; i <= n; i ++ ) smax[i] = max(smax[i - 1], p[i].y);
for(int i = n; i; i -- ) smin[i] = min(smin[i + 1], p[i].y);
//记录答案
int res = 0;
for(int i = 1; i <= n; i ++ )
//比较两个数组
if(p[i].y < smin[i + 1] && p[i].y > smax[i - 1])
res ++ ;
cout << res << endl;
return 0;
}