Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2018
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <string>
  5.  
  6. struct FootballPlayer {
  7. size_t number;
  8. uint32_t efficiency;
  9. };
  10.  
  11. void HeapExtractMin(std::vector<FootballPlayer>::iterator heap_begin, size_t size, const std::string& comparator) {
  12. if (size <= 1) {
  13. return;
  14. }
  15. FootballPlayer tmp = {(*(heap_begin + size - 1)).number, (*(heap_begin + size - 1)).efficiency};
  16. (*(heap_begin + size - 1)).number = (*heap_begin).number;
  17. (*(heap_begin + size - 1)).efficiency = (*heap_begin).efficiency;
  18. (*(heap_begin)).number = tmp.number;
  19. (*(heap_begin)).efficiency = tmp.efficiency;
  20. if (size == 2) {
  21. return;
  22. } else if (size == 3) {
  23. if (!playerLess(*heap_begin, *(heap_begin + 1), comparator)) {
  24. tmp = {(*(heap_begin)).number, (*(heap_begin)).efficiency};
  25. (*(heap_begin)).number = (*(heap_begin + 1)).number;
  26. (*(heap_begin)).efficiency = (*(heap_begin + 1)).efficiency;
  27. (*(heap_begin + 1)).number = tmp.number;
  28. (*(heap_begin + 1)).efficiency = tmp.efficiency;
  29. }
  30. return;
  31. }
  32. size_t j = 0;
  33. while(!playerLessOrEqual(*(heap_begin + j), *(heap_begin + 2 * j + 1), comparator) ||
  34. !playerLessOrEqual(*(heap_begin + j), *(heap_begin + 2 * j + 2), comparator)) {
  35. if (playerLessOrEqual(*(heap_begin + 2 * j + 1), *(heap_begin + 2 * j + 2), comparator)) {
  36. tmp = {(*(heap_begin + j)).number, (*(heap_begin + j)).efficiency};
  37. (*(heap_begin + j)).number = (*(heap_begin + 2 * j + 1)).number;
  38. (*(heap_begin + j)).efficiency = (*(heap_begin + 2 * j + 1)).efficiency;
  39. (*(heap_begin + 2 * j + 1)).number = tmp.number;
  40. (*(heap_begin + 2 * j + 1)).efficiency = tmp.efficiency;
  41. j = 2 * j + 1;
  42. } else {
  43. tmp = {(*(heap_begin + j)).number, (*(heap_begin + j)).efficiency};
  44. (*(heap_begin + j)).number = (*(heap_begin + 2 * j + 2)).number;
  45. (*(heap_begin + j)).efficiency = (*(heap_begin + 2 * j + 2)).efficiency;
  46. (*(heap_begin + 2 * j + 2)).number = tmp.number;
  47. (*(heap_begin + 2 * j + 2)).efficiency = tmp.efficiency;
  48. j = 2 * j + 2;
  49. }
  50. if (2 * j + 1 >= size - 1) {
  51. return;
  52. } else if (2 * j + 2 >= size - 1) {
  53. if (!playerLessOrEqual(*(heap_begin + j), *(heap_begin + 2 * j + 1), comparator)) {
  54. tmp = {(*(heap_begin + j)).number, (*(heap_begin + j)).efficiency};
  55. (*(heap_begin + j)).number = (*(heap_begin + 2 * j + 1)).number;
  56. (*(heap_begin + j)).efficiency = (*(heap_begin + 2 * j + 1)).efficiency;
  57. (*(heap_begin + 2 * j + 1)).number = tmp.number;
  58. (*(heap_begin + 2 * j + 1)).efficiency = tmp.efficiency;
  59. }
  60. return;
  61. }
  62. }
  63. };
  64.  
  65. void HeapSort(std::vector<FootballPlayer>::iterator heap_begin, std::vector<FootballPlayer>::iterator heap_end, const std::string& comparator) {
  66. size_t size = heap_end - heap_begin;
  67. for (size_t i = 0; i != size; ++i) {
  68. HeapExtractMin(heap_begin, size - i, comparator);
  69. }
  70. };
  71.  
  72. int main() {
  73. uint32_t n = 0;
  74. std::vector<FootballPlayer> all_players;
  75. std::vector<FootballPlayer> result_team;
  76. uint32_t max_score;
  77. uint32_t player = 0;
  78. std::cin >> n;
  79. for (uint32_t i = 0; i != n; ++i) {
  80. std::cin >> player;
  81. FootballPlayer footbal_player = {player, i + 1};
  82. HeapInsert(all_players, footbal_player, "playerEfficiencyLess");
  83. }
  84.  
  85. HeapSort(all_players.begin(), all_players.end(), "playerEfficiencyLess");
  86. return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement