UVaLive 6694 Toy Boxes (二分+想法)

题意：给出n个数，把n个数放在三个盒子里，每个盒子里的数绑在一起，要拿出来任何一个数的时候，所承担的重量是整个盒子的总重量，求最小总重量和。

析：感觉吧，就是轻的放的多一些，拿的次数多一些，大的放的少一些，拿的少一些。分成两堆时一定是连续小的物品在一堆，连续大的在一堆，

也就是其中一堆的任意一个物品重量都要小于另一堆。,并且小的那一堆的个数一定要大于大的那一堆的个数。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <functional>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <deque>

#include <map>

#include <cctype>

#include <stack>

#include <sstream>

#include <cstdlib>

#define freopenr freopen("in.txt", "r", stdin)

#define freopenw freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 0x3f3f3f3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 2e4 + 5;

const int mod = 1e9 + 7;

const char *mark = "+-*";

const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};

const int dc[] = {0, 1, 0, -1, -1, 1, 1, -1};

int n, m;

inline int Min(int a, int b){ return a < b ? a : b; }

inline int Max(int a, int b){ return a > b ? a : b; }

inline LL Min(LL a, LL b){ return a < b ? a : b; }

inline LL Max(LL a, LL b){ return a > b ? a : b; }

int a[maxn];

LL sum[maxn];

bool cmp(const int &lhs, const int &rhs){

    return lhs > rhs;

}

int main(){

    int T;    cin >> T;

    while(T--){

        scanf("%d", &n);

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

        sort(a+1, a+n+1, cmp);

        sum[1] = a[1];

        for(int i = 2; i <= n; ++i)  sum[i] = a[i] + sum[i-1];

        LL ans = LNF;

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

            for(int j = i+1; j <= n*2/3; ++j){

                int k = n - j;

                ans = Min(ans, sum[i]*(i) + (sum[j]-sum[i])*(j-i) + (sum[n]-sum[j]) * k);

            }

        }

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

    }

    return 0;

}