Liebig's Barrels CodeForces

大意:给定$nk$块木板, 要制作$n$个$k$块板的桶, 要求任意两桶容积差不超过$l$, 每个桶的容积为最短木板长, 输出$n$个桶的最大容积和

假设最短板长$m$, 显然最后桶的体积都在$[m,m+l]$范围内, 就是说需保证每个桶都至少有一块板在$[m,m+l]$范围.

考虑贪心逐步调整, 假设$m+l$足够多的话, 可以先尽量连续得选最短的边做桶, 最后将$m+l$分给剩余桶即为最大容积.

如果不够多的话, 就要选出$m+l-1$分给剩余桶, 还不够就选择$m+l-2$, 直到所有桶都分到为止.

离散化后预处理一下前缀和可以达到复杂度$O(nlogk+nlogn)$

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;

typedef long long ll;

const int N = 4e5+10, INF = 0x3f3f3f3f;

int n, k, l;

int a[N], b[N], cnt[N], s[N];

//用a记录离散化后的值, b是离散化辅助数组

//cnt记录每个离散化后的值的出现次数, s统计cnt的前缀和

ll solve(int n, int x) {

	//当前最大的为x, 还要制作n个桶的最大容积和

	int t = (s[x-1]+k-1)/k;

	if (t+cnt[x]>=n) {

		//x数量足够, 直接贪心分配

		ll ans = 0;

		REP(i,1,n) {

			if (a[(i-1)*k+1]<x) ans += b[a[(i-1)*k+1]];

			else ans += b[x];

		}

		return ans;

	}

	//x不够的话, 先尽量把x分完, 求出第一个比x小的数, 递归计算

	auto p = lower_bound(a+1,a+1+n*k,x);

	return solve(n-cnt[x],*(--p))+(ll)cnt[x]*b[x];

}

int main() {

	scanf("%d%d%d", &n, &k, &l);

	REP(i,1,n*k) scanf("%d", a+i);

	sort(a+1,a+1+n*k);

	ll mx = a[1]+l;

	if (a[n]>mx) return puts("0"),0;

	REP(i,1,n*k) b[i]=a[i];

	*b = unique(b+1,b+1+n*k)-b-1;

	REP(i,1,n*k) a[i]=lower_bound(b+1,b+1+*b,a[i])-b;

	REP(i,1,n*k) ++cnt[a[i]];

	REP(i,1,*b) s[i]=s[i-1]+cnt[i];

	int p = upper_bound(b+1,b+1+*b,mx)-b-1;

	printf("%lld\n", solve(n,p));

}

看了下别人题解, 发现没必要这么麻烦, 上述分析已经知道, 最优结构一定是先连续选一段最小的, 再将$[m,m+l]$中剩余的逐个分给剩余桶

假设连续部分做了x个桶, 剩余部分y个桶, 就有$xk+y<=s[m+l],x+y=n$

解出x的最大值, 就可以直接得到最优解的结构了

巴特西

Liebig's Barrels CodeForces - 985C (贪心)

最新文章

热门文章