AcWing 1978. 奶牛过马路

AcWing 1978. 奶牛过马路

思路：用bi的前缀最大值和后缀最大值判断当前线段是否相交 代码：

#include 
#include 
#include 
using namespace std;
typedef pair PII;
#define x first
#define y second
const int N = 100010,INF=1e8;
int smax[N],smin[N];
PII p[N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d%d", &p[i].x, &p[i].y);
    
    sort(p+1,p+1+n);
    smax[0]=-INF,smin[n+1]=INF;
    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>smax[i-1]&&p[i].y					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5703194.html