#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; vector<int> NUMS; bool biggerNum(int &e1, int &e2) { if (NUMS[e1] != NUMS[e2]) { return(NUMS[e1] > NUMS[e2]); } else { return(e1 > e2); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //vector<int> NUMS; for (int i = 0; i < 500000; i++) { NUMS.push_back(0); } // int most = 0; int n; cin >> n; for (int i = 0; i < n; i++) { int x; cin >> x; ++NUMS[x - 1]; if (x > most) {most = x;} //cout << "\nx:" << x << " most:" << most; } // vector<int> sorted; for (int i = 0; i < most; i++) { sorted.push_back(i); } sort(sorted.begin(), sorted.end(), biggerNum); // // /* <-- add second / befor * to unlock; remove second / to lock for (size_t i = 0; i < sorted.size(); i++) { cout << sorted[i] + 1 << "\n"; } //*/ int counter = 0; while (true) { ++counter; //cout << "\nleader: " << sorted[0] + 1; int liders = NUMS[ sorted[0] ]; --liders; //cout << " | searching for " << liders << " numbers, found: "; NUMS[ sorted[0] ] = 0; sorted.erase( sorted.begin() ); while (liders > 0) { if (sorted.size() == 0) { break; } while (NUMS[ sorted[sorted.size() - 1] ] == 0) { sorted.pop_back(); if (sorted.size() == 0) { break; } } if (sorted.size() == 0) { break; } --liders; //cout << sorted[ sorted.size() - 1 ] + 1 << ","; --NUMS[ sorted[ sorted.size() - 1 ] ]; while (NUMS[ sorted[sorted.size() - 1] ] == 0) { sorted.pop_back(); if (sorted.size() == 0) { break; } } if (sorted.size() == 0) { break; } } if (sorted.size() == 0) { break; } } cout << /*"\ncounter: " <<*/ counter; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; vector<int> NUMS; bool biggerNum(int &e1, int &e2) { if (NUMS[e1] != NUMS[e2]) { return(NUMS[e1] > NUMS[e2]); } else { return(e1 > e2); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //vector<int> NUMS; for (int i = 0; i < 500000; i++) { NUMS.push_back(0); } // int most = 0; int n; cin >> n; for (int i = 0; i < n; i++) { int x; cin >> x; ++NUMS[x - 1]; if (x > most) {most = x;} //cout << "\nx:" << x << " most:" << most; } // vector<int> sorted; for (int i = 0; i < most; i++) { sorted.push_back(i); } sort(sorted.begin(), sorted.end(), biggerNum); // // /* <-- add second / befor * to unlock; remove second / to lock for (size_t i = 0; i < sorted.size(); i++) { cout << sorted[i] + 1 << "\n"; } //*/ int counter = 0; while (true) { ++counter; //cout << "\nleader: " << sorted[0] + 1; int liders = NUMS[ sorted[0] ]; --liders; //cout << " | searching for " << liders << " numbers, found: "; NUMS[ sorted[0] ] = 0; sorted.erase( sorted.begin() ); while (liders > 0) { if (sorted.size() == 0) { break; } while (NUMS[ sorted[sorted.size() - 1] ] == 0) { sorted.pop_back(); if (sorted.size() == 0) { break; } } if (sorted.size() == 0) { break; } --liders; //cout << sorted[ sorted.size() - 1 ] + 1 << ","; --NUMS[ sorted[ sorted.size() - 1 ] ]; while (NUMS[ sorted[sorted.size() - 1] ] == 0) { sorted.pop_back(); if (sorted.size() == 0) { break; } } if (sorted.size() == 0) { break; } } if (sorted.size() == 0) { break; } } cout << /*"\ncounter: " <<*/ counter; return 0; } |