2015多校第6场 HDU 5360 Hiking 贪心，优先队列

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

题意：给定n个人，现在要邀请这些人去远足，但每个人同意邀请的条件是当前已经同意去远足的人数c必须满足c>=l[i]&&c<=r[i](l[i]、r[i]为第i个人同意去远足的条件界限，分别表示要求当前已经同意去远足的人数至少l[i]个人，至多r[i]个人)，问你邀请的顺序是什么才能使尽可能多的人去远足，若有多个最优解，输出任意的一个。

解法：优先队列贪心，具体做法如下：如果把题目中的人数看做数轴上的点的话，那么应该按照从0依次递增的顺序来选择区间，把符合条件的区间预先存起来，然后按照他们的终点由小到大排序，第一个就是我们要的区间，如果遇到第一个区间的终点也小于当前值，那么也将他放入ans数组，只不过被邀请的人数不变而已。显然，看到这种思路就应当往优先队列的角度考虑。这里应当首先对区间按照起点大小排序（若相同则按照终点大小排序）。然后起点小的先进入优先队列，出队列时，终点小的先出队列即可。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

struct node{

    int l,r,id;

    node(){}

    node(int l, int r, int id):l(l),r(r),id(id){}

    bool operator < (const node &rhs) const{

        return r>rhs.r;

    }

}a[maxn];

bool cmp(node x, node y){

    if(x.l==y.l) return x.r<y.r;

    return x.l<y.l;

}

int T, n;

int main()

{

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        for(int i=1; i<=n; i++) scanf("%d", &a[i].l), a[i].id = i;

        for(int i=1; i<=n; i++) scanf("%d", &a[i].r);

        sort(a+1, a+n+1,cmp);

        priority_queue<node,vector<node> >q;

        vector<int>ans;

        int t = 0, cur = 1;

        while(1){

            while(cur <= n && a[cur].l <= t){//当前区间起点<=当前值，入队

                q.push(a[cur]);

                cur++;

            }

            while(!q.empty()&&q.top().r<t){//如果队首元素的终点<=当前值，说明不能被邀请，同理也不影响邀请人数t

                ans.push_back(q.top().id);

                q.pop();

            }

            if(q.size()==0) break;

            else{

                ans.push_back(q.top().id);

                q.pop();

            }

            t++;

        }

        printf("%d\n", t);

        while(cur<=n){

            ans.push_back(a[cur].id);

            cur++;

        }

        for(int i=0; i<ans.size(); i++){

            printf("%d", ans[i]);

            if(i==(int)(ans.size()-1)) printf("\n");

            else printf(" ");

        }

    }

    return 0;

}

巴特西

2015多校第6场 HDU 5360 Hiking 贪心，优先队列

最新文章

热门文章