题目链接:
UVALive 6694 - Toy Boxes
题意:
有 n 个物品,需要分在三个箱子里,每个箱子的花费是
分析:
先考虑将其分为两堆的情况。我们需要证明一个结论:分成两堆时一定是连续小的物品在一堆,连续大的在一堆,也就是其中一堆的任意一个物品重量都要小于另一堆。,并且小的那一堆的个数一定要大于大的那一堆的个数。
假设一堆的个数为 x ,重量为
① x<y 且第一堆的每一件物品 xi 的重量都小于第二堆的任意一件物品 yj
从第二堆中任取一个 yj ,重量为 b 放进第一堆中
原有的总花费为:x?A+y?B
调整后:(x+1)?(A+b)+(y?1)?(B?b)=x?A+y?B+b?(x?y)+A+b?B+b=x?A+y?B+b?(x?y)+(2?b?(B?A))
因为 x<y 且第一堆的每一件物品 xi 的重量都小于第二堆的任意一件物品 yj ,那么 B?A>b,2?b?(B?A)<b ,同时 x?y<?1,b?(x?y)<?b ,那么b?(x?y)+(2?b?(B?A))<0
所以调整后更优。② x>y 且第一堆的每一件物品 xi 的重量 a 大于第二堆的一件物品
yj 重量 b
原有的总花费是:x?A+y?B
交换后的花费是:x?(A?a+b)+y?(B?b+a)=x?A+y?B+(y?x)?(a?b)
显然调整后更优。
这样子可以粗略的证明了上述结论。对于分成两堆的情况,先排序然后扫一遍即可。那么分成三堆呢?我们可以枚举第一堆的个数 i ,然后二分查找第二堆的个数,因为花费关于个数是一个单峰函数。比较
注意开 long long 。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <climits>
#include <ctime>
using namespace std;
typedef long long ll;
const int MAX_N = 20010;int T, n;
ll data[MAX_N], sum[MAX_N];inline ll solve(int t, int x) //t是第二堆的个数
{int a = t, b = n - (x + t);ll A = sum[x + a] - sum[x], B = sum[n] - sum[x + a];return A * a + B * b;
}inline ll check(int x)
{ int low = 1, high = n - x - 1, mid;ll tmp1, tmp2; while(low < high - 10) {mid = (low + high) / 2;tmp1 = solve(mid, x);++mid;tmp2 = solve(mid, x);if(tmp1 > tmp2) low = mid;else high = mid - 1;}ll res = min(solve(low, x), solve(high, x));for(int i = low + 1; i < high; ++i) {res = min(res, solve(i, x));}return res;
}int main()
{scanf("%d", &T);while(T--) {scanf("%d", &n);for(int i = 1; i <= n; ++i) scanf("%lld", &data[i]);sort(data + 1, data + n + 1);for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + data[i];ll ans = sum[n] * n;for(int i = 1; i <= n - 2; ++ i) {ans = min(ans, sum[i] * i + check(i));// printf("i = %d ans = %d\n", i, ans);}if(n <= 3) ans = sum[n];printf("%lld\n", ans);}return 0;
}