hdu 5306 Hiking || 2015 Multi-University Training Contest 六 (优先队列 为小疯子而生）

hdu 5306 Hiking 请戳

1. 题意：
   请邀请n个小疯子去疯，ta们名字分别为1…n；小疯子脾气都很怪，每个小疯子都需要你满足条件：只要在邀请ta之前，可以保证至少有 l 个人并且顶多就 r 个，ta才去。（你后面再邀请到全体中国人去都和他的决定没关系，小疯子版口香糖 嘻嘻！）
   要求给出一起疯的最大人数，并且给出邀请的顺序。

2. 思路：
   先对每个小疯子的下限做升序，然后再用优先队列（stl中 priority_queue）对 这些小疯子取最小上限用作队列的比较。（前提是要满足上下限条件哈！）
   好了， 去邀请小疯子们吧！

3. 复杂度：
   时间复杂度：O（nlog（n））
   空间复杂度：O（n）

4. 邀请小疯子代码

/* ***********************************************
Author        :Ilovezilian
Created Time  :2015/8/7 19:52:48
File Name     :1008_1.cpp
 ************************************************ */

#include <bits/stdc++.h>
#define fi(i,n1,n) for(int i = n1; i <= n; i ++)
#define fd(i,n1,n2) for(int i = n1; i >= n2; i --)
#define INF 0x7fffffff  
#define ll long long
using namespace std;
const int N = 100100, mod = 1e9+7;

int n, ans;
struct nod {
    int l, r, o;
}p[N];

bool cmp(nod a, nod b) {return a.l < b.l;}
struct cmp1 { bool operator () (nod a, nod b){return a.r > b.r;}};

priority_queue<nod, vector<nod>, cmp1> q;

void judge()
{
    int i = 0, m = 0;
    ans = 0;
    for(; i < n; i ++)
    {
        while(m < n && p[m].l <= i) q.push(p[m]), m ++;
        while(!q.empty() && q.top().r < i) q.pop();
        if(q.empty())
        {
            while(!q.empty()) q.pop();
            return;
        }
        if(!q.empty()) ans ++, q.pop();
    }
    while(!q.empty()) q.pop();
    return;
}

void solve()
{
    scanf("%d", &n);
    fi(i,0,n-1) p[i].o = i + 1;
    fi(i,0,n-1) scanf("%d", &p[i].l);
    fi(i,0,n-1) scanf("%d", &p[i].r);
    sort(p, p + n, cmp);
    judge();
    printf("%d\n", ans);

    if(ans == 0)
    {
        fi(i,0, n - 1) printf("%d%c", p[i].o, i != n - 1 ? ' ' : '\n');
        return;
    }

    int i = 0, m = 0, cnt = 1;
    for(; i < n; i ++)
    {
        while(m < n && p[m].l <= i) q.push(p[m]), m ++;
        while(!q.empty() && q.top().r < i) printf("%d%c" ,q.top().o, cnt ++ != n ? ' ' : '\n'), q.pop();
        if(!q.empty())
        {
            printf("%d%c" ,q.top().o, cnt ++ != n ? ' ' : '\n');
            q.pop();
        }
    }
    while(!q.empty())
    {
         printf("%d%c" ,q.top().o, cnt ++ != n ? ' ' : '\n');
         q.pop();
    }
}

int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int  cas;
    scanf("%d", &cas);
    while(cas --) solve();  
    return 0;
}