意甲冠军：
n个月格儿 所有的格龙或公主的儿子 从勇士1走n 不杀 杀死有钱拿 路过公主 假设之前杀龙的数量满足公主要求就会停止行走 问 勇士想多拿钱 可是必需要满足n格子的公主 最多拿多少钱
思路：
公主仅仅限制杀龙的数量 因此不想停下来结婚就控制杀龙的数量就可以 假设要放弃一些龙 那么一定会贪心放弃钱少的龙 最后推断一下能不能和n格子的公主结婚就可以
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
#define N 200010 int n;
struct dragon {
int x, id;
bool operator<(const dragon ff) const {
return x > ff.x;
}
} now;
priority_queue<dragon> q;
int ans[N], tot, sum; int main() {
int i, k, s;
char who[100];
while (!q.empty())
q.pop();
scanf("%d", &n);
for (i = 2; i <= n; i++) {
scanf("%s%d", who, &k);
if (i == n)
break;
if (who[0] == 'd') {
now.x = k;
now.id = i;
q.push(now);
} else {
s = q.size();
if (s >= k) {
k = s - k + 1;
while (k--)
q.pop();
}
}
}
s = q.size();
if (s < k)
printf("-1\n");
else {
tot = sum = 0;
while (!q.empty()) {
now = q.top();
q.pop();
sum += now.x;
ans[tot++] = now.id;
}
printf("%d\n", sum);
printf("%d\n", tot);
sort(ans, ans + tot);
for (i = 0; i < tot; i++)
printf("%d%s", ans[i], (i == tot - 1) ? "\n" : " ");
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。