http://codeforces.com/contest/313/problem/C

贪心，构造性问题

题意：一开始看错了以为是一个直接递归就能解决的问题，后来才发现，是要构造一个矩阵。给了4^n个数字，然后让你利用这些数字构造出一个2^n*2^n的方阵，并且令到这个方阵的beauty值最大。

一个方阵的beauty值是这样定义的，这个方阵如果只有一个元素，那么它的beauty值就是这个元素，当然这个方阵里面的最大元素也是它。如果这个方阵不止一个元素，这个方阵一定能分割为4个等大的小方阵（因为保证是2^n*2^n的。一定可分割），大方阵的beauty值等于4个小方阵的beauty值相加，再加上大方针中最大元素。你的目的是要构造一个方阵，让它的beauty值最大

bea值的计算递归即可，但是细想一下bea值的计算过程就能得到构造的策略

会发现，方阵中的每个元素都会最后的beauty值做出贡献，但是不同元素做出的贡献不同

好像1个2*2的方阵，3个元素对方阵的bea值贡献了1次，而最大值元素则贡献了2次。如果方阵规模再大点，会发现一些元素贡献了4次，一些元素贡献了3次，一些2次，一些1次

所以为了使beauty值最大，我们让较大的元素贡献的次数多一点，这样就能令最大的beauty更大（这就是本题贪心的部分）

下面举几个例子

1*1规模的矩阵

1个元素贡献了1次

2*2规模的矩阵

1个元素贡献2次，3个元素贡献1次

4*4规模的矩阵

1个元素贡献3次，3个元素贡献2次，12个元素贡献1次

8*8规模的矩阵

1个元素贡献4次，3个元素贡献3次，12个元素贡献2次，48个元素贡献1次

 

规律更明显了，我们只要用一些数组把规律保存下来，就能直接使用，具体看代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N  = 2000010;ll a[N],M[30],C[30],sum[30];bool cmp(ll x ,ll y){    return x > y;}int main(){    M[1] = 1;    for(int i=2; i<=15; i++) M[i] = M[i-1] * 4;    C[1] = 1; C[2] = 3;    for(int i=3; i<=15; i++) C[i] = C[i-1] * 4;    sum[0] = 0; sum[1] = 1;    for(int i=2; i<=15; i++) sum[i] = sum[i-1] + C[i];    int tot,n;    cin >> tot;    for(int i=1; i<=tot; i++)        cin >> a[i];    sort(a+1,a+1+tot,cmp);        for(int i=1; true ;i++)         if(tot == M[i]){            n = i; break;        }    //n是它的规模    ll res = 0;    int i=0 , j , k , m = n;    for(k=1; i<=tot ;k++)    {        for(i=sum[k-1]+1; i<=sum[k] && i<=tot; i++)            res += a[i] * m;        m--;    }    cout << res << endl;    return 0;}