Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <string>
- struct FootballPlayer {
- size_t number;
- uint32_t efficiency;
- };
- void HeapExtractMin(std::vector<FootballPlayer>::iterator heap_begin, size_t size, const std::string& comparator) {
- if (size <= 1) {
- return;
- }
- FootballPlayer tmp = {(*(heap_begin + size - 1)).number, (*(heap_begin + size - 1)).efficiency};
- (*(heap_begin + size - 1)).number = (*heap_begin).number;
- (*(heap_begin + size - 1)).efficiency = (*heap_begin).efficiency;
- (*(heap_begin)).number = tmp.number;
- (*(heap_begin)).efficiency = tmp.efficiency;
- if (size == 2) {
- return;
- } else if (size == 3) {
- if (!playerLess(*heap_begin, *(heap_begin + 1), comparator)) {
- tmp = {(*(heap_begin)).number, (*(heap_begin)).efficiency};
- (*(heap_begin)).number = (*(heap_begin + 1)).number;
- (*(heap_begin)).efficiency = (*(heap_begin + 1)).efficiency;
- (*(heap_begin + 1)).number = tmp.number;
- (*(heap_begin + 1)).efficiency = tmp.efficiency;
- }
- return;
- }
- size_t j = 0;
- while(!playerLessOrEqual(*(heap_begin + j), *(heap_begin + 2 * j + 1), comparator) ||
- !playerLessOrEqual(*(heap_begin + j), *(heap_begin + 2 * j + 2), comparator)) {
- if (playerLessOrEqual(*(heap_begin + 2 * j + 1), *(heap_begin + 2 * j + 2), comparator)) {
- tmp = {(*(heap_begin + j)).number, (*(heap_begin + j)).efficiency};
- (*(heap_begin + j)).number = (*(heap_begin + 2 * j + 1)).number;
- (*(heap_begin + j)).efficiency = (*(heap_begin + 2 * j + 1)).efficiency;
- (*(heap_begin + 2 * j + 1)).number = tmp.number;
- (*(heap_begin + 2 * j + 1)).efficiency = tmp.efficiency;
- j = 2 * j + 1;
- } else {
- tmp = {(*(heap_begin + j)).number, (*(heap_begin + j)).efficiency};
- (*(heap_begin + j)).number = (*(heap_begin + 2 * j + 2)).number;
- (*(heap_begin + j)).efficiency = (*(heap_begin + 2 * j + 2)).efficiency;
- (*(heap_begin + 2 * j + 2)).number = tmp.number;
- (*(heap_begin + 2 * j + 2)).efficiency = tmp.efficiency;
- j = 2 * j + 2;
- }
- if (2 * j + 1 >= size - 1) {
- return;
- } else if (2 * j + 2 >= size - 1) {
- if (!playerLessOrEqual(*(heap_begin + j), *(heap_begin + 2 * j + 1), comparator)) {
- tmp = {(*(heap_begin + j)).number, (*(heap_begin + j)).efficiency};
- (*(heap_begin + j)).number = (*(heap_begin + 2 * j + 1)).number;
- (*(heap_begin + j)).efficiency = (*(heap_begin + 2 * j + 1)).efficiency;
- (*(heap_begin + 2 * j + 1)).number = tmp.number;
- (*(heap_begin + 2 * j + 1)).efficiency = tmp.efficiency;
- }
- return;
- }
- }
- };
- void HeapSort(std::vector<FootballPlayer>::iterator heap_begin, std::vector<FootballPlayer>::iterator heap_end, const std::string& comparator) {
- size_t size = heap_end - heap_begin;
- for (size_t i = 0; i != size; ++i) {
- HeapExtractMin(heap_begin, size - i, comparator);
- }
- };
- int main() {
- uint32_t n = 0;
- std::vector<FootballPlayer> all_players;
- std::vector<FootballPlayer> result_team;
- uint32_t max_score;
- uint32_t player = 0;
- std::cin >> n;
- for (uint32_t i = 0; i != n; ++i) {
- std::cin >> player;
- FootballPlayer footbal_player = {player, i + 1};
- HeapInsert(all_players, footbal_player, "playerEfficiencyLess");
- }
- HeapSort(all_players.begin(), all_players.end(), "playerEfficiencyLess");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement