codeforces E. 专题竞赛 +二分or倒序优化(数组离散化)

题目链接：http://codeforces.com/contest/1077/problem/E
题目大意：有 n 个竞争性编程问题，每个问题必须属于某个专题。
现在要举办几场主题比赛。每个比赛中的所有问题应该具有相同的主题，并且所有比赛应该具有两两不同的主题。他可能不会使用所有问题。

Polycarp希望连续几天举办比赛，每天一场比赛。Polycarp希望通过以下方式举办一系列比赛：

1.每场比赛的问题数量正好是前一次比赛（一天前）的两倍，第一2.每场比赛可以包含任意数量的问题;
3.应该最大化所有比赛中的问题总数。

专题1有4个问题
专题2有5个问题
专题10有9个问题
最大化问题总数的举办方法：2->4->8

思路：但时没有写到这道题，但听说是二分。开始写的时候准备二分枚举第一天的题目数目，写完了才发现不对，S=f(x) x与S不是相关关系(正相关or负相关)，就是说第一天的题目数目与题目总数没有相关关系。所以二分不了。但是想到暴力的复杂度不是O(n·n)，因为题目的专题和某个专题的最大题目数不可能同时为n，可以暴力试试。T54了。

int er(int mid)/*mid：第一天的题目数*/
{
    long long ans=0;
    for(int i=0;i<cnt&&s[i]!=0;i++)/*s[i]：第i个专题的题目数*/
    {
        if(s[i]>=mid)
        {
            ans+=mid;
            mid*=2;
        }
    }
    sum=max(sum, ans);
}

然后队友想了一种优化方法：枚举最后一天的题目数，这种方法的可以形成一个可行性剪枝。如果第i天应该有的mid题目数，而实际的题目数是s[i]<mid，那么就可以不往i-1搜索因为s[k],k=[0, i)都小于s[i]。
而正向搜索，s[i]<mid，但是s[k]，k=[i, n)有可能有>=mid的，所以必须搜索完。

优化后：跑了109ms

int er(int mid)/*最后一天的题目数*/
{
    long long ans=0;
    for(int i=cnt-1;i>=0;i--)
    {
        if(s[i]>=mid)
        {
            ans+=mid;
            if(mid%2==0)
                mid/=2;
            else/*mid为奇数则已经是第一天了*/
                break;

        }
        else/*可行性剪枝*/
            break;
    }
    sum=max(sum, ans);
}

当然看了别人的题解，二分也是可以的，也跑了109ms

int er(int mid)
{
    long long ans=0, w=0;
    while(1)
    {
        int p=lower_bound(s+w, s+cnt, mid)-s;/*二分找到第一个大等于mid的天数*/
        if(p==cnt)
            break;

        ans+=mid;
        mid*=2;
        w=p+1;/*移动二分的左端点*/
    }
    sum=max(sum, ans);
}

因为专题的编号<=10^9，为了方便统计数量，就离散化了一下。可以不离散化的，复杂度比较高但是能AC。

思考：虽然前面才做了两道二分的题，但是这题知道是二分还是没有想出来，因为之前都是先二分再搜索O(lgn · n)，这题是先搜索再二分O(n · lgn)。
只有s与i有相关系，那么就可以二分i找到最优的s。

#include<bits/stdc++.h>
using namespace std;

//n原数组大小 a原数组中的元素 ls离散化的数组 cnt离散化后的数组大小 
int a[200005], ls[200005], n, cnt;
long long sum=0;
int s[200005];

void lsh()/*数组离散化*/
{
    sort(a, a+n);
    cnt=unique(a, a+n)-a;

    for(int i=0;i<n;i++)
        ls[i]=lower_bound(a, a+cnt, ls[i])-a;

}

/*二分*/
int er(int mid)
{
    long long ans=0, w=0;
    while(1)
    {
        int p=lower_bound(s+w, s+cnt, mid)-s;
        if(p==cnt)
            break;

        ans+=mid;
        mid*=2;
        w=p+1;
    }
    sum=max(sum, ans);
}

/*优化搜索*/
//int er(int mid)/*最后一天的题目数*/
//{
//    long long ans=0;
//    for(int i=cnt-1;i>=0;i--)
//    {
//        if(s[i]>=mid)
//        {
//            ans+=mid;
//            if(mid%2==0)
//                mid/=2;
//            else/*mid为奇数则已经是第一天了*/
//                break;
//
//        }
//        else/*可行性剪枝*/
//            break;
//    }
//    sum=max(sum, ans);
//}

int main()
{
    fill(s, s+200005, 0);
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]), ls[i]=a[i];

    lsh();

    for(int i=0;i<n;i++)
    {
        s[ls[i]]++;
    }

    sort(s, s+cnt);

    int l=1; int r=*max_element(s, s+n);
    for(int i=l;i<=r;i++)
    {
        er(i);
    }

    cout<<sum<<endl;

    return 0;
}