白駿[102]宝石盗賊C++解

白駿[102]宝石泥棒
アイデア

グリディアルゴリズム

が使用されます

Multiset

が使用されます

low bound

が使用されます
に答える

multiset格納袋

を用いる.

宝石の情報をベクトルに格納しsortでソートする

宝石の価値を大きな値から調査(本人は負の数で保存)し、bag中のlow boundでbagの重量反復器

を求める

end()でなければ見つけられ、それに応じた値を付けて袋に使われているバッグを削除します.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <math.h>
#include <set>
#define ll long long

using namespace std;

multiset<int> bag;
vector<pair<int, int>> crystal;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int m,v; // m == weight, v == cost
		cin >> m >> v;
		crystal.push_back({ -v,m });
	}

	for (int i = 0; i < k; i++) {
		int c;
		cin >> c;
		bag.insert(c);
	}

	sort(crystal.begin(), crystal.end());

	ll answer = 0;

	for (auto iter = crystal.begin(); iter != crystal.end(); iter++) {

		if (bag.size() == 0) break;

		int crystal_value = -((*iter).first);
		int crystal_weight = (*iter).second;

		auto bag_iter = bag.lower_bound(crystal_weight);

		if (bag_iter != bag.end()) {
			answer += crystal_value;
			bag.erase(bag_iter);
		}

	}

	cout << answer << endl;

	return 0;
}

評価
GRADYアルゴリズム自体を考えることは非常に容易な問題である.
でもタイムアウトの時に苦労する人が多いと思います
計算はlow boundによりO(logn)により行うことができる.
priority queueを使用する方法もありますので、参照することをお勧めします.
setが重複値を保存できないため、筆者には別のエラーがあります.
ずっと間違っていると言っていた(袋の重さが同じなら)
したがって、この問題は、複数セットで繰り返しを許可することによって解決されます.