题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=548
题目意思：
有一个骑士，要经过n个房间，开始在第一个房间，每个房间里面有龙或者公主，遇到龙，可以决定杀或者不杀，如果杀，就可以得到相应的珠宝；如果遇到公主，如果这个骑士此时杀过的龙的数目大于等于公主的美貌值，那么这个骑士必须marry这个公主，不能拒绝．．^_^，但是骑士的真爱是在最后一个房间里面的公主，问骑士能不能到达最后一个房间？如果能的话，求出能够到达最后一个房间的情况下，得到的最大的珠宝数．
做法：
优先队列＋贪心．
遇到龙就杀，用优先队列维护得到的珠宝数目，遇到公主就检查目前的杀的龙的数目是不是大于等于公主的美貌值，如果大于等于，就把有限队列里面珠宝值小的房间出队，直到杀的龙的数目小于美貌值为止．
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct Node {
int pos, n;
bool operator < (const Node &other) const {
return n < other.n;
}
}node;
int array[];
priority_queue<Node> a;
char ch[];
int main(void) {
int i, n, tmp, j, sum, cnt;
while (~scanf("%d", &n)) {
sum = , cnt = , j = , i = ;
for (int f = ; f < n-; ++f, ++j, ++i) {
scanf("%s%d", ch, &tmp);
node.pos = i, node.n = -tmp;
if (ch[] == 'd') {
a.push(node); cnt++; sum += tmp;
}
else {
while (!a.empty() && cnt >= tmp) {
int hehe = a.top().n; a.pop(); cnt--; sum += hehe;
}
}
}
scanf("%s%d", ch, &tmp);
if (cnt >= tmp) {
printf("%d\n%d\n", sum, cnt);
int e = ;
while (!a.empty()) {
array[e++] = a.top().pos; a.pop();
}
sort(array, array+e);
for (int i = ; i < e; ++i) {
printf("%d", array[i]);
if (i != e-) printf(" ");
}
printf("\n");
}
else printf("-1\n");
} return ;
}
这题想明白就行了，可惜比赛的时候没有时间做．．．＝＝