Codeforces 1077E Thematic Contests（二分）

题意：给出n道有类型的题目，每天组织一场专题比赛，该天题目数量必须是前一天的2倍，第一天的题目数量可以任意选择，求能消耗的最多题目数量。

题解：先整理成不同类型的序列，接着把对应类型题目的数量扔进vector，排序。枚举第一天题目数量，vector从当前位置往下找符合的下一个位置，不断把题目数量翻两倍，过程中记录总题目数量，同时维护最多题目数量。

 1 #include <map>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 const int N=2e5+10;
10 map <int,int> m;
11 vector <int> v,b;
12 int vsize,bsize;
13 
14 int cal(int x){
15     int sum=0;
16     int pos=0;
17     while(1){
18         pos=(lower_bound(b.begin()+pos,b.end(),x)-b.begin());
19         if(pos==bsize) break;
20         pos++;sum+=x;
21         x*=2;
22     }
23     return sum;
24 }
25 
26 int main(){
27     int n,x,mx=0,ans=0;
28     scanf("%d",&n);
29     for(int i=1;i<=n;i++){
30         scanf("%d",&x);
31         if(!m[x]) v.push_back(x);
32         m[x]++;
33         mx=max(mx,m[x]);
34     }
35     bsize=vsize=v.size();
36     for(int i=0;i<vsize;i++) b.push_back(m[v[i]]);
37     sort(b.begin(),b.end());
38     for(int i=1;i<=mx;i++) ans=max(ans,cal(i));
39     printf("%d
",ans);
40     return 0;
41 }

View Code