【题解】Codeforces 985C 【Liebig’s Barrels】

2018年5月22日 签到题

【题意】需要造n个桶,每个桶需要k个木板,桶的容积等于最短的板的高度,任意两个桶容积之差不超过 l ,你有n * k个木板,长度已知,问能否造出符合条件的n个桶,如果能的话问这n个桶的容积之和最大是多少,如果不能的话就输出0

 

贪心,搜索过不了

分析加代码参照@LucienShui

首先对木板升序排序,显然我们至少可以让前n个木板恰好为n个桶的容积,判断一下a_{n} - a_{1}\leq l,是否成立,不成立就输出0。

我们发现,如果我们让每连续的k个木板形成一个桶的话,那么这些桶的容积将会是a_{1},a_{k+1},a_{2k+1},...中间一些较小的木板都会被更短但是又必须得取的木板给包含,这样一定是最优的。

首先我们找到一个最大的upper,使得a_{upper}-a_{1} \leq l(upper \leq n \times k)成立,这样在[1,upper]的范围内以任意n个木板的高度为桶的容积都是合法的。假设此时我们选了x个连续的k来造桶,还需要再造y个桶才能造够n个桶,则有:

x \times k + y \leq upper
x + y = n

移项、代入、化简:

x \leq \frac{upper - n}{k - 1}

也就是说:得到x后,y也就相应出来了,对于剩下的upper - x \times k个木板,显然取后y-1个和第x \times k + 1个木板作为剩下的y个桶的容积是最优的。

#include <bits/stdc++.h>

typedef long long int64;
const int MAXN = (int)1e5 + 7;

int64 a[MAXN];

int main() {
	int64 n,k,l,m,ans,upper;
    scanf("%I64d %I64d %I64d", &n, &k, &l);
    m = n * k;
    
    for (int i = 1; i <= m; i++){
    	scanf("%I64d", &a[i]);
	}
    std::sort(a + 1, a + 1 + m);
    
    if (a[n] - a[1] > l){
    	return 0 * puts("0");
	} 
    if (k == 1){
    	for(int i = 1; i <= n; i++) {
    		ans += a[i];
		}
	}
    else {
        while (a[upper] - a[1] <= l && upper <= m){
        	upper++;
		} 
        upper--;
        
        int64 x = (upper - n) / (k - 1);
        
		for (int i = 1, cur = 1; i <= x; i++, cur += k) {
			ans += a[cur];
		}
        for (int i = 1; i < n - x; i++) {
        	ans += a[upper--];
		}
        ans += a[x * k + 1];
    }
    printf("%I64d\n", ans);
    return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注