#include <bits/stdc++.h> using namespace std; #ifdef LOCAL template <class T, class U> ostream& operator<<(ostream& os, pair<T, U> p) { return os << "(" << p.first << ", " << p.second << ")"; } template<template<class, class...> class C, class... A> typename enable_if<!is_same<C<A...>, string>::value, ostream&>::type operator<<(ostream& os, C<A...> c) { auto i = c.begin(); while (i != c.end()) { os << " {"[i == c.begin()] << *i; os << ",}"[++i == c.end()]; } return os; } #define debug(x) { cerr << #x << " = " << x << endl; } #else #define debug(...) {} #endif vector<int> counter; inline void add(int x) { if (counter.size() <= x) counter.resize(x + 1); counter[x] ++; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++) { int a; scanf("%d", &a); add(a); } for (int i = 0; i < counter.size(); i ++) { for (int j = 1; (1<<j) <= counter[i]; j ++) { if ((1<<j) & counter[i]) add(i + j); } } printf("%d\n", (int)counter.size() - 1); }
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 | #include <bits/stdc++.h> using namespace std; #ifdef LOCAL template <class T, class U> ostream& operator<<(ostream& os, pair<T, U> p) { return os << "(" << p.first << ", " << p.second << ")"; } template<template<class, class...> class C, class... A> typename enable_if<!is_same<C<A...>, string>::value, ostream&>::type operator<<(ostream& os, C<A...> c) { auto i = c.begin(); while (i != c.end()) { os << " {"[i == c.begin()] << *i; os << ",}"[++i == c.end()]; } return os; } #define debug(x) { cerr << #x << " = " << x << endl; } #else #define debug(...) {} #endif vector<int> counter; inline void add(int x) { if (counter.size() <= x) counter.resize(x + 1); counter[x] ++; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i ++) { int a; scanf("%d", &a); add(a); } for (int i = 0; i < counter.size(); i ++) { for (int j = 1; (1<<j) <= counter[i]; j ++) { if ((1<<j) & counter[i]) add(i + j); } } printf("%d\n", (int)counter.size() - 1); } |