Thematic Contests CodeForces - 1077E

http://codeforces.com/contest/1077/problem/E

序列给定  自己选个首项 问最大能凑出多大的前n项和

把出现次数升序排序 枚举首项 然后暴力向后二分即可 因为总数不超过n logn次内肯定结束

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;

struct node
{
    int val,cnt;
};

node ary[maxn];
int tmp[maxn];
int n,maxx;

bool cmp(node n1,node n2)
{
    return n1.cnt<n2.cnt;
}

int solve()
{
    int res,sum,i,p,cur,l,r,m,gou;
    for(i=1;i<=n;i++) maxx=max(maxx,ary[i].cnt);
    res=0;
    for(i=1;i<=maxx;i++){
        sum=0,p=1,cur=i;
        while(1){
            l=p,r=n,gou=-1;
            while(l<=r){
                m=(l+r)/2;
                if(cur<=ary[m].cnt) r=m-1,gou=m;
                else l=m+1;
            }
            if(gou==-1) break;
            sum+=cur,p=gou+1,cur*=2;
        }
        res=max(res,sum);
    }
    return res;
}

int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&tmp[i]);
    sort(tmp+1,tmp+n+1);
    for(i=1,j=0;i<=n;i++){
        if(j==0||tmp[j]!=tmp[i]){
            tmp[++j]=tmp[i];
            ary[j].val=tmp[j],ary[j].cnt=1;
        }
        else ary[j].cnt++;
    }
    n=j;
    sort(ary+1,ary+n+1,cmp);
    printf("%d\n",solve());
    return 0;
}