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 × 2- 大小的子矩阵，那么 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 = *1e6 + ;

 int matrix[maxn];

 int main()

 {

     int i, j, n;

     __int64 ans, sum;

     while (scanf("%d", &n) != EOF)

     {

         for (i = ; i <= n; i++)

             scanf("%d", &matrix[i]);

         sort(matrix+, matrix++n);

         ans = sum = ;

         for (j=i=; i <= n; j <<= )

         {

             for ( ; i <= j; i++)  // 就是图中的1，2，3

                 sum += matrix[n-i+];

             ans += sum;

         }

         printf("%I64d\n", ans);

     }

     return ;

 }