奶牛过马路(排序+前缀最值)

题目描述:

奶牛过马路(排序+前缀最值)
奶牛过马路(排序+前缀最值)

主要思路:

如何判断两个奶牛过马路的路线是否有交点呢?
奶牛过马路(排序+前缀最值)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
typedef pair<int,int> pa;
const int N=1e5+10;
pa a[N];
set<int> b;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].first>>a[i].second;
    int ans=n;
    sort(a+1,a+1+n);
    int maxb=-1e6,maxi=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].second<maxb)
        {
            b.insert(i);
            b.insert(maxi);
        }
        else
        {
            maxb=a[i].second;
            maxi=i;
        }
    }
    int minb=1e6,mini=0;
    for(int i=n;i;i--)
    {
        if(a[i].second>minb)
        {
            b.insert(i);
            if(mini)
                b.insert(mini);
        }
        else
        {
            minb=a[i].second;
            mini=i;
        }
    }
    ans-=b.size();
    cout<<ans<<endl;
    return 0;
}
上一篇:【原创】运维基础之Docker(3)搭建私有仓库


下一篇:java_eclipse_设置全局编码_utf-8_编译class指定_运行jar乱码解决_不依赖环境