HDU 5360 우선 대기 열

클릭 하여 링크 열기
제목: n 개인 에 대해 선택 한 순 서 를 써 서 마지막 에 참가 하 는 사람 이 가장 많 습 니 다. 현재 의 사람 에 게 참가 하 는 조건 은 이미 참가 한 사람 이 L 보다 많 고 그의 R 보다 적 으 며 여러 가지 상황 이 수출 을 만족 시 킬 수 있 습 니 다.
사고방식: 어떻게 하면 인원수 가 가장 많 을 수 있 는 지 생각해 보 자. 예 를 들 어 현재 참가 한 인원 이 ans 개 라면 모든 L 이 ans 보다 적 고 참가 하지 않 은 사람 이 다 해 볼 수 있다. 그러면 이렇게 많은 사람들 이 어느 것 이 가장 좋 은 지 선택 할 수 있다. 당연히 R 을 선택 한 가장 작은 만족 이 ans 와 같은 사람 보다 크다. 이런 사람들 은 우선 대기 열 로 저장 하면 된다. 만족 하 는 것 을 찾 으 면 뛰 어 나온다.그렇지 않 으 면 ans 의 팝 업 을 만족 시 키 지 못 할 것 입 니 다. ans 개 를 만족 시 키 지 못 할 것 입 니 다. ans 이후 의 그것 은 더욱 만족 하지 않 을 것 입 니 다.

#include <queue>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const int maxn=100010;
int L[maxn],R[maxn];
int vis[maxn],vis1[maxn];
struct number1{
    int x,pos;
    bool operator < (const number1 &a) const {return x>a.x;}
};
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        memset(vis1,0,sizeof(vis1));
        number1 nn;
        scanf("%d",&n);
        priority_queue<number1>qu;
        priority_queue<number1>que[100010];
        for(int i=1;i<=n;i++){
            scanf("%d",&L[i]);
            if(L[i]>n) L[i]=n+1;
        }
        for(int i=1;i<=n;i++) scanf("%d",&R[i]);
        for(int i=1;i<=n;i++){
            nn.x=R[i];nn.pos=i;
            que[L[i]].push(nn);
        }
        int ans=0;
        for(int i=0;i<=n;i++){
            int flag=0;
            while(!que[i].empty()){
                nn=que[i].top();que[i].pop();
                qu.push(nn);
            }
            while(!qu.empty()){
                nn=qu.top();qu.pop();
                if(nn.x>=ans){
                    vis[ans++]=nn.pos;vis1[nn.pos]=1;
                    flag=1;break;
                }
            }
            if(flag==0) break;
        }
        printf("%d
",ans);
        for(int i=0;i<ans;i++) printf("%d ",vis[i]);
        for(int i=1;i<=n;i++) if(vis1[i]==0) printf("%d ",i);
        printf("
");
    }
    return 0;
}