HDU 5360 Hiking(2015多校联合)(优先队列)

HDUOJ 优先队列

题目链接

戳我

题目大意

soda想要邀请 n 个人去旅行,但是这 但是 第 $i$个人去旅行的条件是当前 soda 邀请的总人数 $sum$ 必须满足 $l_i <= r_i$,这个人才会去和soda一起旅行
问 soda最多能邀请的人数,输出 人数,以及邀请顺序

Note: beta will always tell the truth and soda will agree if and only if the number he hears is no less than li and no larger than ri, otherwise he will disagree. Once soda agrees to go hiking he will not regret even if the final total number fails to meet some soda's will.

即soda不会说假话,只要满足这个人的条件,他就会同意,即使后来的人数不满足他的条件了,他也不能反悔

样例解释

4 // T,测试样例个数, $T <= 600$
8 // n, $1 <= n <= 10^5$
4 1 3 2 2 1 0 3 // $l_i$, 即分别为第i个人的区间的 $l$
5 3 6 4 2 1 7 6 // $r_i$, 即分别为第i个人的区间的 $r$
输出:
7 //soda最多能邀请到的人数, 是 7 个
1 7 6 5 2 4 3 8 // 邀请顺序,$1$不可能被邀请,要先输出(也可以最后输出),即先邀请 7号,在邀请 6.....
邀请顺序可能有多种情况,输出任意一种,但是 最多邀请的人数一定是固定的

解题思路

贪心.

Solution
- sort all the people according to $l_{i}$and $r_{i}$
- maintain an integer $cur$ as the number of people agree to go out yet. For all the people will agree to go out, pick the one with smallest $r$.
官方题解

即先对 l r排序
对于一个 $sum$ 找到 所有符合的区间,即所有能同意的人, 从这些区间挑出 r 最小的即可.
可用优先队列
比赛时AC 300+, 都怪太粗心了,写完忘记测样例就直接交了,导致一直T没有发现,最后发现已晚~~(>_<)~~

//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
#define LL long long
using namespace std;
const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
struct Soda
{
    int l, r;
    int id;
    bool operator < (const Soda &a) const
    {
        if(l == a.l) return r < a.r; //l同, r小的在前
        return l < a.l;  //l小的在前
    }
}soda[maxn];
int ha[maxn], nu[maxn], n;
struct F
{
    int id;
    int r;
    F(int id, int r):id(id),r(r){}
    bool operator < (const F &a) const
    {
        return r > a.r; //优先队列按照r小的在前
    }
};
priority_queue<F>q;
void slove()
{
    if(soda[1].l != 0)
    {
        printf("0\n");
        for(int i = 1; i <= n; i++)
        {
            if(i == 1) printf("%d", i);
            else printf(" %d", i);
        }
        puts("");
        return;
    }
    int sum = 0;
    int k = 0, i = 1;
    while(1)
    {
        while(!q.empty() && q.top().r < sum) q.pop();
        for(; i <= n; i++)
        {
            if(soda[i].l > sum) break;
            q.push(F(soda[i].id, soda[i].r));
        }
        if(q.empty()) break;
        nu[k++] = q.top().id;
        q.pop();
        ha[nu[k-1]] = 1;
        sum++;
    }
    printf("%d\n", k);
    for(i = 0; i < k; i++)
    {
        if(i == 0) printf("%d", nu[i]);
        else printf(" %d", nu[i]);
    }    
    for(i = 1; i <= n; i++)
    {
        if(!ha[i])
        {
            printf(" %d", i);
            //if(i != n-k) printf(".");
        }
    }
    printf("\n");
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &soda[i].l);
            soda[i].id = i;
            ha[i] = 0;
        }        
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &soda[i].r);
        }
        sort(soda, soda+n+1);
        slove();
    }
    return 0;
}