#include <algorithm> #include <cstdio> #include <map> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define VAR(v,w) __typeof(w) v=(w) #define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it) #define PB push_back #define ALL(c) (c).begin(),(c).end() #define SIZE(c) ((int)(c).size()) #define SD second #define INT(x) int x; scanf("%d", &x) typedef vector<int> VI; int main() { INT(n); map<int, int> m; REP(i,n) { INT(a); ++m[a]; } VI v; v.reserve(SIZE(m)); FORE(it,m) v.PB(it->SD); sort(ALL(v), greater<int>()); int ii = 0, jj = SIZE(v) - 1, r = 0; while (ii < jj) { int k = v[ii++] - 1; while (jj >= ii) { if (v[jj] > k) { v[jj] -= k; break; } k -= v[jj]; v[jj--] = 0; } ++r; } if (v[ii]) ++r; printf("%d\n", r); }
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 | #include <algorithm> #include <cstdio> #include <map> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define VAR(v,w) __typeof(w) v=(w) #define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it) #define PB push_back #define ALL(c) (c).begin(),(c).end() #define SIZE(c) ((int)(c).size()) #define SD second #define INT(x) int x; scanf("%d", &x) typedef vector<int> VI; int main() { INT(n); map<int, int> m; REP(i,n) { INT(a); ++m[a]; } VI v; v.reserve(SIZE(m)); FORE(it,m) v.PB(it->SD); sort(ALL(v), greater<int>()); int ii = 0, jj = SIZE(v) - 1, r = 0; while (ii < jj) { int k = v[ii++] - 1; while (jj >= ii) { if (v[jj] > k) { v[jj] -= k; break; } k -= v[jj]; v[jj--] = 0; } ++r; } if (v[ii]) ++r; printf("%d\n", r); } |