SGU 548 Dragons and Princesses

意甲冠军：

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;

}