贪心+优先队列 HDOJ 5360 Hiking

题目传送门

 /*
题意:求邀请顺序使得去爬山的人最多,每个人有去的条件
贪心+优先队列:首先按照l和r从小到大排序,每一次将当前人数相同的被邀请者入队,那么只要能当前人数比最多人数条件小,该人能 被邀请,而且不用考虑最少人数的条件。网上的写的比我简洁,学习了。
详细解释:http://blog.csdn.net/queuelovestack/article/details/47319361
*/
/************************************************
* Author :Running_Time
* Created Time :2015-8-6 14:51:47
* File Name :H.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 MAXN = 1e5 + ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
struct Node {
int l, r, id;
bool operator < (const Node &x) const {
return r > x.r;
}
}node[MAXN];
priority_queue<Node> Q;
bool vis[MAXN];
int ans[MAXN];
int n; bool cmp(Node x, Node y) {
if (x.l == y.l) return x.r < y.r;
return x.l < y.l;
} int main(void) { //HDOJ 5360 Hiking
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i=; i<=n; ++i) {
scanf ("%d", &node[i].l); node[i].id = i;
}
for (int i=; i<=n; ++i) {
scanf ("%d", &node[i].r);
}
sort (node+, node++n, cmp); if (node[].l != ) {
puts ("");
for (int i=; i<=n; ++i) printf ("%d%c", i, (i==n) ? '\n' : ' ');
continue;
}
memset (vis, false, sizeof (vis));
while (!Q.empty ()) Q.pop ();
int i = , p = ;
for (; i<=n && p==node[i].l; ++i) Q.push (node[i]);
while (!Q.empty ()) {
while (!Q.empty ()) {
if (p <= Q.top ().r) {
ans[++p] = Q.top ().id;
vis[ans[p]] = true; Q.pop (); break;
}
else Q.pop ();
}
for (; i<=n && p==node[i].l; ++i) Q.push (node[i]);
} printf ("%d\n", p);
printf ("%d", ans[]);
for (int i=; i<=p; ++i) {
printf (" %d", ans[i]);
}
for (int i=; i<=n; ++i) {
if (!vis[i]) printf (" %d", i);
}
puts ("");
} return ;
}
上一篇:使用 postman 给 API 写测试


下一篇:eclipse中导入jsp等工程使用过程中常遇问题