Codeforces 1077E Thematic Contests(二分)

题目链接:Thematic Contests

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

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

 #include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
const int N=2e5+;
map <int,int> m;
vector <int> v,b;
int vsize,bsize; int cal(int x){
int sum=;
int pos=;
while(){
pos=(lower_bound(b.begin()+pos,b.end(),x)-b.begin());
if(pos==bsize) break;
pos++;sum+=x;
x*=;
}
return sum;
} int main(){
int n,x,mx=,ans=;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&x);
if(!m[x]) v.push_back(x);
m[x]++;
mx=max(mx,m[x]);
}
bsize=vsize=v.size();
for(int i=;i<vsize;i++) b.push_back(m[v[i]]);
sort(b.begin(),b.end());
for(int i=;i<=mx;i++) ans=max(ans,cal(i));
printf("%d\n",ans);
return ;
}
上一篇:C和指针---读书笔记。


下一篇:介绍 Active Directory 域服务 (AD DS) 虚拟化