codeforces C. Ilya and Matrix 解题报告

题目链接：http://codeforces.com/problemset/problem/313/C

题目意思：给定 4ⁿ 个整数（可以组成 2ⁿ × 2ⁿ 大小的矩阵），问通过对这些整数进行排列，求出 the resulting maximum beauty of the matrix。这个最大值的定义是这样的：先定义m为所有整数中的最大值。如果n = 0，那么，这个beauty 数就是m；否则把2ⁿ × 2ⁿ 大小的矩阵划分为  2^n - 1 × 2^n - 1- 大小的子矩阵，那么 beauty 数是：m + 其余4个子矩阵的beauty数。

      举个例子吧，假设输入的 4ⁿ 为16，16个整数为： 1 3 5 9 9 20 3 7 41 30 1 4 5 10 9 7。先排序，然后可以抽象成这样解决：（数字表示第几步要相加的和）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int maxn = 2*1e6 + 10;
int matrix[maxn];

int main()
{
    int i, j, n;
    __int64 ans, sum;
    while (scanf("%d", &n) != EOF)
    {
        for (i = 1; i <= n; i++)
            scanf("%d", &matrix[i]);
        sort(matrix+1, matrix+1+n);
        ans = sum = 0;
        for (j=i=1; i <= n; j <<= 2)
        {
            for ( ; i <= j; i++)  // 就是图中的1，2，3
                sum += matrix[n-i+1];
            ans += sum;
        }
        printf("%I64d
", ans);
    }
    return 0;
}