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

题意：

大概的意思就是每个人有个人数接受范围$[l_i,r_i]$，现在你每次能从还未被选取的人中选择一个人，如果当前人数符合这个人的需求，那么这个人就会被选中。现在让你输出一个选择的序列，使得被选择的人数尽量多。

题解：

就贪心就好，总的来说就是人数不断增大的时候，每次从可行的所有$l$中选择$r$最小的那个。至于为什么这样是最优的。。需要脑补。

代码：

#include<iostream>

#include<queue>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

#include<functional>

#define MAX_N 100005

using namespace std;

struct node {

public:

    int val;

    int pos;

    node(int v, int p) : val(v), pos(p) { }

    node() { }

    bool operator<(const node &a) const {

        return val > a.val;

    }

};

priority_queue<node> que;

int n;

int T;

vector<node> L[MAX_N];

vector<int> G;

int l[MAX_N],r[MAX_N];

bool used[MAX_N];

void init() {

    for (int i = ; i <= n; i++)L[i].clear();

    memset(used,,sizeof(used));

    G.clear();

    while (que.size())que.pop();

}

int main() {

    scanf("%d", &T);

    while (T--) {

        scanf("%d", &n);

        init();

        for (int i = ; i < n; i++)

            scanf("%d", &l[i]);

        for (int i = ; i < n; i++)

            scanf("%d", &r[i]);

        for (int i = ; i < n; i++)

            L[l[i]].push_back(node(r[i], i + ));

        int ans = ;

        for (int i = ; i <= n; i++) {

            for (int j = ; j < L[i].size(); j++)que.push(L[i][j]);

            while (que.size() && que.top().val < i)que.pop();

            if (que.empty()) {

                ans = i;

                break;

            }

            G.push_back(que.top().pos);

            que.pop();

        }

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

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

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

            used[G[i]] = ;

        }

        for (int i = ; i <= n; i++)if (!used[i])printf("%d ", i);

        printf("\n");

    }

    return ;

}

巴特西

HDOJ 5360 Hiking 优先队列+贪心

题意：

题解：

代码：

最新文章

热门文章