2018-10-20 2 分钟读完 (大约 355 个字)

Moiezen

题面

$MYC$ 带着他的行李去考清华集训了。对 $MYC$ 来说,进候选队不在话下。。。
$MYC$ 有 $n$ 件行李,编号为 $1,2,…,n$。行李的质量是模 $P$ 意义下的($P$ 不一定是质数)。$MYC$有 $k$ 个背包,要装下这些行李,为了方便 $MYC$ 在背包中找行李,每个背包中的行李编号是连续的,允许有背包为空。$MYC$ 想让最重的背包尽量轻。
由于 $MYC$ 毕竟是要进候选队的人,他有特技可以用。他会选择一个 $x(0<=x<P)$,给所有行李的质量$+x$并$\%P$,然后才装到背包里去。
你要帮助 $MYC$ 先选择一个 $x$,再选择一种行李分配方案,使得最重的背包尽量轻。
$MYC$ 相信,你一定能帮他装好行李,给拼搏于候选队的逐梦之路上的 $MYC$,提供一个有力的援助。

题解

~~随机化~~

考虑暴力，枚举$x$，二分背包最小重量即可

时间复杂度$O(Pnlogn)$，跑不过

考虑剪枝：如果在二分之前$check(ans)$非法，那么当前这个方案一定不可行。

于是$random_shuffle$一下保证时间复杂度：$O($跑得过$)$

#include<cstdio>
#include<climits>
#include<algorithm>
#include<ctime>
#define RG register
using namespace std;

inline int read()
{
	int data = 0, w = 1;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data*w;
}

const int maxn(10010);
int n, P, k, ans, a[maxn], _max, d[maxn];

inline bool check(int mid, int x)
{
	for(RG int i = 1, w = 0, t, cnt = 1; i <= n; i++)
	{
		t = (a[i] + x) % P;
		if(mid < t) return false;
		if(w + t > mid) ++cnt, w = 0;
		if(cnt > k) return false;
		w += t;
	}
	return true;
}

inline void Solve(int x)
{
	_max = 0;
	for(RG int i = 1; i <= n; i++) _max = max(_max, (a[i] + x) % P);
	int l = _max, r = 1e8 + 1, res = r;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(check(mid, x)) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	ans = min(ans, res);
}

int main()
{
	srand(time(NULL));
	n = read(); P = read(); k = read();
	for(RG int i = 1; i <= n; i++) a[i] = read();
	for(RG int i = 1; i <= P; i++) d[i] = i - 1;
	ans = 1e8; random_shuffle(d + 1, d + P + 1);
	for(RG int i = 1; i <= P; i++)
	{
		if(!check(ans, d[i])) continue;
		Solve(d[i]);
	}
	printf("%d\n", ans);
	return 0;
}

Algorithm --- 二分答案, Algorithm --- 贪心, 其它 --- 随机化

Moiezen

题面

题解

标签

Your browser is out-of-date!