贪心求Hack
查看原帖
贪心求Hack
1014544
supernoobbb楼主2024/5/17 14:10
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mx=1e6+3;
typedef struct{int l,r;}item;
inline void solve()
{
    int n;
    cin>>n;
    unordered_map<int,int>ma;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        if(ma[l]==0)ma[l]=r;
        else ma[l]=min(ma[l],r);
    }
    stack<item>sta;
    for(int i=0;i<=mx;i++)
    {
        if(!ma[i])continue;
        item t;
        t.l=i,t.r=ma[i];
        if(!sta.empty()){
            while(ma[i]<=sta.top().r)
            {
                sta.pop();
                if(sta.empty())break;
            }
        }
        if(sta.empty())
        {
            sta.push(t);
            continue;
        }
        if(i>=sta.top().r)sta.push(t);
    }
    cout<<sta.size();
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

2024/5/17 14:10
加载中...