Pagini recente » Cod sursa (job #2969797) | Cod sursa (job #143196) | Cod sursa (job #3163432) | Cod sursa (job #1458413) | Cod sursa (job #2987736)
#include <iostream>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;
pair<int, int> find_left_son(vector<pair<int, int>> heap, int root_index) {
if (root_index * 2 > heap.size() - 1) return make_pair(-1, -1);
return heap[root_index * 2 + 1];
}
pair<int, int> find_right_son(vector<pair<int, int>> heap, int root_index) {
if (root_index * 2 + 1 > heap.size() - 1) return make_pair(-1, -1);
return heap[root_index * 2 + 2];
}
vector<pair<int, int>> create_max_heap(vector<pair<int, int>> heap) {
int heap_size = heap.size();
for (int i = heap_size - 1; i > 0; i--) {
if (heap[i].second >= heap[i / 2].second) swap(heap[i], heap[i / 2]);
}
return heap;
}
int main()
{
ifstream fin("lup.in");
ofstream fout("lup.out");
vector<pair<int, int>> sheep;
int sheep_count, wolf_max_step, sheep_step_back;
fin >> sheep_count >> wolf_max_step >> sheep_step_back;
for (int i = 0; i < sheep_count; i++) {
int wool_quantity, distance;
fin >> distance >> wool_quantity;
sheep.push_back(make_pair(distance, wool_quantity));
}
// to maximize the wool quantity we will use a greedy aproach:
// take the first sheep available(that can be reached by the wolf) from a max-heap based on wool quantity
vector<pair<int, int>> sheep_max_heap = create_max_heap(sheep);
int total_wool = 0, steps_by_wolf = 0;
while (!sheep_max_heap.empty()) {
if (steps_by_wolf * sheep_step_back + sheep_max_heap[0].first <= wolf_max_step) {
total_wool += sheep_max_heap[0].second;
steps_by_wolf++;
}
sheep_max_heap.erase(sheep_max_heap.begin());
sheep_max_heap = create_max_heap(sheep_max_heap);
};
fout << total_wool;
return 0;
}