HDOJ 5360 Hiking 【优先队列】

HDOJ 5360 Hiking 【priority_queue】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5360

题目就是说有n个人，
每个人有自己的编号以及自己在被邀请时可以接受的当前的人数范围[l, r]
要求确定一个邀请序列，使得同意加入队列的人数最多

标记一个cnt计数当前已经同意邀请的人数，
然后把所有人的数组按照l从小到大排序，
当l ≤ cnt 时表示此人有可能同意邀请，加入优先队列
对于所有优先队列里的人按照r从小到大排序
当r ≥ cnt 是表示此人可以同意邀请，
并且按照最优策略，应该就是r ≥ cnt 并且最接近cnt的那个人此时被邀请
所以将优先队列中不符合要求的人直接丢出（因为加入队列且不符合要求的人在下一个情况中也不可能符合要求了）
然后将符合要求的队列第一项加入结果集即可

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;
#define clr(c) memset(c, 0, sizeof(c));
#define pi acos(-1.0)
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef struct soda{
    int l, r;
    int i; // i-th
    bool operator < (const soda& s) const{
        return l < s.l;
    }
    bool operator > (const soda& s) const { return s < *this; }
}s;
struct cmp{ // 最小值优先
    bool operator ()(s &s1,s &s2){
        return s1.r>s2.r; // 若return值为true, 就交换s1 s2的位置
    }
};
const int MAXL = 1e5+5;
s soda[MAXL];
bool vis[MAXL];
int order[MAXL];
int T, n;
int cnt;
int start;
int leftstart;
priority_queue<s, vector<s>, cmp> q;

void Resolve(){
    clr(vis); // clear
    clr(order); // clear
    while(!q.empty()) q.pop(); // clear
    sort(soda+1, soda+1+n);
    cnt = 0;
    start = 1;

    //for(int i = 1; i <= n; i++) printf("%d %d, %d
", soda[i].l, soda[i].r, soda[i].i);

    for(int i = 1; i <= n; i++){
        for( ; start <= n && soda[start].l <= cnt; start++){ // l符合要求的进队
            q.push(soda[start]);
        }
        while(!q.empty() && q.top().r < cnt){ // r不符合要求的丢出去
            q.pop();
        }
         if(!q.empty()){
            //printf("q.top().i %d
", q.top().i);
            order[cnt++] = q.top().i;
            vis[q.top().i] = true;
            q.pop();
         }
    }
    leftstart = cnt;
    for(int i = 1; i <= n; i++){
        if(vis[i] == false){
            order[leftstart++] = i;
        }
    }
    //OUTPUT
    printf("%d
", cnt);
    for(int i = 0; i < n; i++){
        printf("%d", order[i]);
        if(i != n-1) printf(" ");
    }
    printf("
");
}

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &soda[i].l);
        for(int i = 1; i <= n; i++) scanf("%d", &soda[i].r);
        for(int i = 1; i <= n; i++) soda[i].i = i;
        Resolve();
    }

    return 0;
}