//#pragma GCC optimize("Ofast", "unroll-loops") //#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4") #include <bits/stdc++.h> #define all(a) a.begin(),a.end() #define len(a) (int)(a.size()) #define mp make_pair #define pb push_back #define fir first #define sec second #define fi first #define se second using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef long double ld; template<typename T> bool umin(T &a, T b) { if (b < a) { a = b; return true; } return false; } template<typename T> bool umax(T &a, T b) { if (a < b) { a = b; return true; } return false; } #ifdef KIVI #define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false) #define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl template<class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); } #else #define DEBUG while (false) #define LOG(...) #endif mt19937 rng(4242); const int max_n = -1, inf = 1000111222; void solve() { int n; cin >> n; vector<int> a(n); vector<int> am(n); for(auto& x : a) { cin >> x; am[--x]++; } sort(all(am)); reverse(all(am)); int can = 0; int ans = 0; while(can < n) { can += am[ans] * 2 - 1; ans++; } cout << ans << '\n'; } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) solve(); } /* KIVI */
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 | //#pragma GCC optimize("Ofast", "unroll-loops") //#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4") #include <bits/stdc++.h> #define all(a) a.begin(),a.end() #define len(a) (int)(a.size()) #define mp make_pair #define pb push_back #define fir first #define sec second #define fi first #define se second using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef long double ld; template<typename T> bool umin(T &a, T b) { if (b < a) { a = b; return true; } return false; } template<typename T> bool umax(T &a, T b) { if (a < b) { a = b; return true; } return false; } #ifdef KIVI #define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false) #define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl template<class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); } #else #define DEBUG while (false) #define LOG(...) #endif mt19937 rng(4242); const int max_n = -1, inf = 1000111222; void solve() { int n; cin >> n; vector<int> a(n); vector<int> am(n); for(auto& x : a) { cin >> x; am[--x]++; } sort(all(am)); reverse(all(am)); int can = 0; int ans = 0; while(can < n) { can += am[ans] * 2 - 1; ans++; } cout << ans << '\n'; } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) solve(); } /* KIVI */ |