HDU5360——优先队列——Hiking

Problem Description

There are

, 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.

Help beta design an invitation order that the number of soda who agree to go hiking is maximum.

Input

There are multiple test cases. The first line of input contains an integer

It is guaranteed that the total number of soda in the input doesn't exceed 1000000. The number of test cases in the input doesn't exceed 600.

Output

For each test case, output the maximum number of soda. Then in the second line output a permutation of

denoting the invitation order. If there are multiple solutions, print any of them.

Sample Input

4 8 4 1 3 2 2 1 0 3 5 3 6 4 2 1 7 6 8 3 3 2 0 5 0 3 6 4 5 2 7 7 6 7 6 8 2 2 3 3 3 0 0 2 7 4 3 6 3 2 2 5 8 5 6 5 3 3 1 2 4 6 7 7 6 5 4 3 5

Sample Output

7 1 7 6 5 2 4 3 8 8 4 6 3 1 2 5 8 7 7 3 6 7 1 5 2 8 4 0 1 2 3 4 5 6 7 8

Source

2015 Multi-University Training Contest 6

/*
大意：n个人参加一个活动的条件有人数限制，l和r，问你最多有多少个人能一起去，把不能参加的人随便输出
用优先队列维护满足的情况
把块从0分到n，贪心地把r最小的并且满足大于等于l的值取出，注意判断如果这一次没有了，下一次也肯定没有这种情况
*/
/************************************************
Author        :powatr
Created Time  :2015-8-6 14:45:47
File Name     :b.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAX = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct edge{
    int l, r, id;
}a[MAX];
struct edge1{
    int x, y;
};
edge1 P;

struct cmp1
{
    bool operator () (edge1 x, edge1 y)
    {
        return x.x > y.x;
    }
};

int b[MAX];
int vis[MAX];
int n;
vector<edge1>G[MAX];

int main(){
    int T;
    priority_queue < edge1 , vector<edge1> , cmp1 > q;
    scanf("%d", &T);
    while(T--){
        memset(vis, 0, sizeof(vis));
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i++){
            scanf("%d",&a[i].l);
        }
        for(int i = 0 ; i <= 100000; i++)
            G[i].clear();
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i].r);
        for(int i = 1; i <= n; i++)
            a[i].id = i;
        // sort(a + 1, a + n + 1);

         while(!q.empty()) q.pop();

        for(int i = 1; i <= n; i++)
            G[a[i].l].push_back((edge1){a[i].r, a[i].id});

        for(int i = 0 ; i < G[0].size(); i++)
            q.push((edge1){G[0][i].x,G[0][i].y});
        int ans = 1;
        edge1 m;
        if(!q.empty()){
            m = q.top();
         if(m.x >= 0){
           b[ans++] = m.y;
            q.pop();
         }
        }
            
        for(int i = 1; i <= n; i++){

            for(int j = 0; j < G[i].size(); j++)
                q.push((edge1){G[i][j].x, G[i][j].y});
           // if(ans < i + 2) break;
            while(!q.empty()){
                m = q.top();
               if(ans < i + 1) break;
               if(ans == i + 2) break;
                if(m.x >= i){
                q.pop();
                b[ans++] = m.y;
            }
                else q.pop();
            }
        }
        printf("%d
", ans - 1);
        for(int i = 1; i < ans ; i++){
            printf("%d ", b[i]);
            vis[b[i]] = 1;
        }
         for(int i = 1 ; i <= n; i++)
             if(!vis[i])
                    printf("%d ", i);
         puts("");
    }
    return 0;
}

　重载

struct Node {
     int l, r, id; 
    bool operator < (const Node &x) const {
        return r > x.r;
    }
}node[MAXN];

HDU5360——优先队列——Hiking

相关推荐