Atcoder214E Packing Under Range Regulations（带悔贪心）

57 阅读 0 评论 38 点赞

我是靠谱客的博主背后蚂蚁，最近开发中收集的这篇文章主要介绍Atcoder214E Packing Under Range Regulations（带悔贪心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接
在这里插入图片描述
题目大意：
我们现在有一个无穷多的箱子，从1开始编号。对于每个物品有个可放编号区间【L,R】一个箱子只能放一个物品。问能否按要求把N个物品都放好。

解题思路：
我们按L排序，开始枚举，并使用优先队列(优先返回最小值)
即每次需要处理最紧急那个物品(r最小)，因为每个物品要放在区间范围以内，初始时指针从最小的L开始，依次处理最需要处理的r ，如果当前r比指针位置要小那么一定无法按要求放完。

 #include<bits/stdc++.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
 using namespace std;
 ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元   (分子*qp(分母,mod-2,mod))%mod;

vector<pair<ll,ll> >s;
signed main(){
    ll t;
    read(t);
    while(t--){
     ll n;
     read(n);
     s.clear();
     for(int i=0;i<n;i++){
     ll x,y;
     read(x);
     read(y);
     s.push_back(mp(x,y));

     }
     sort(s.begin(),s.end());
     priority_queue<ll,vector<ll>,greater<ll> >q;
     s.push_back(mp(inf,inf));
     ll pos=1;
     ll f=0;
     for(int i=0;i<s.size();i++){
        if(f==1)break;

        while(pos<s[i].fi&&q.size()!=0){
            if(q.top()<pos){
            f=1;
            break;
            }
            pos++;
            q.pop();
        }

        pos=s[i].fi;
        q.push(s[i].se);
     }
      if(f){
        printf("Non");
      }
        else{
            printf("Yesn");
        }
    }


}