Codeforces Round #521 (Div. 3)　E. Thematic Contests　(离散化,二分)

题意:有\(n\)个话题,每次都必须选取不同的话题,且话题数必须是上次的两倍,第一次的话题数可以任意,问最多能选取多少话题数.
题解:我们首先用桶来记录不同话题的数量,因为只要求话题的数量,与话题是多少无关,所以我们可以开个新数组然后离散化一下,比如\(mp[5]=6\)可以离散化成\(disc[1]=6\),\(mp[7]=2\)可以离散化成\(disc[2]=2\),这样可以方便我们进行二分查找,然后我们对\(disc\)数组sort一下,从\([1,n]\)开始进行二分,每次去找\(pos\)之后是否第一个大于等于\(now\)的位置,如果没有就break,每次二分都维护一下答案的最大值即可.

代码:

int n;

int x;

map<int,int> mp;

int disc[N];

int cnt;

int res;

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);

    scanf("%d",&n);

    for(int i=1;i<=n;++i){

        scanf("%d",&x);

        mp[x]++;

    }

    for(auto w:mp){

        disc[++cnt]=w.se;

    }

    sort(disc+1,disc+1+cnt);

    for(int i=1;i<=n;++i){

        int sum=0;

        int pos=1;

        int now=i;

        while(true){

            int tmp=lower_bound(disc+pos,disc+1+cnt,now)-disc;

            if(disc[tmp]==0) break;

            sum+=now;

            now*=2;

            pos=tmp+1;

        }

        res=max(res,sum);

    }

    printf("%d\n",res);

    return 0;

}

巴特西

Codeforces Round #521 (Div. 3)　E. Thematic Contests　(离散化,二分)

最新文章

热门文章

巴特西

Codeforces Round #521 (Div. 3) E. Thematic Contests (离散化,二分)

最新文章

热门文章

Codeforces Round #521 (Div. 3)　E. Thematic Contests　(离散化,二分)