@codeforces - 506C@ Mr. Kitayuta vs. Bamboos

@description@
@solution@
@accepted code@
@details@

@description@

n 个竹子，第 i 个竹子初始高度 hi，在每天结束时将长高 ai。

一共 m 天，每天可以砍伐 k 次，可以多次砍伐同一个竹子。如果砍伐的竹子当前高度 h，则砍后变为 max(0, h - p)。

问 m 天之后最高的竹子的高度最小是多少。

原题传送门。

@solution@

考虑第 i 个竹子如果在第 j 天被砍了 \(c_{i,j}\) 次，则最后剩下的高度应为：

\[\max\{h_i + m\times a_i - \sum_{k=1}^{m}c_{i,k}, \ \max_{j=1}^{m}\{(m-j+1)\times a_i - \sum_{k=j+1}^{m}c_{i,k}\}\}
\]

根据砍伐的定义，这是易证的。

我们不妨二分答案 x，前面包含 hi 的式子暴力 O(n) 判断。后面的式子如果暴力判断是 O(nm) 的复杂度。

注意到 k 很小，也就是说总的砍伐数量只有 O(mk) 次，远远小于 O(nm)。

我们不妨只记录对于每棵竹子而言的有效砍伐，使用 m 个队列从后往前进行模拟，就可以做到 O(mk + n) 的判断时间复杂度。

总时间复杂度 O((mk + n)log A)。

@accepted code@

#include <queue>

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

#define fi first

#define se second

#define mp make_pair

const int MAXM = 5000;

const int MAXN = 100000;

int n, m, k;

ll a[MAXN + 5], h[MAXN + 5], p;

queue<pii>que[MAXM + 5];

bool check(ll x) {

	for(int i=1;i<=m;i++) {

		while( !que[i].empty() )

			que[i].pop();

	}

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

		ll s = x / a[i] + 1;

		if( s <= m ) que[s].push(mp(i, 0));

	}

	for(int i=1,c=0;i<=m;i++,c+=k) {

		while( !que[i].empty() ) {

			if( c ) c--; else return false;

			pii f = que[i].front(); que[i].pop(); f.se++;

			ll s = (f.se*p + x) / a[f.fi] + 1;

			if( s <= m ) que[s].push(f);

		}

	}

	ll s = 0;

	for(int i=1;i<=n;i++)

		s += (max(a[i]*m + h[i] - x, 0LL) + p - 1) / p;

	return s <= m*k;

}

int main() {

	scanf("%d%d%d%lld", &n, &m, &k, &p);

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

	ll le = 0, ri = 0;

	for(int i=1;i<=n;i++)

		ri = max(ri, h[i] + m*a[i]);

	while( le < ri ) {

		ll mid = (le + ri) >> 1;

		if( check(mid) ) ri = mid;

		else le = mid + 1;

	}

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

}

@details@

一开始本来想写线段树结果发现会 T，最后还是换成了队列模拟。

注意开 long long 的问题。有些地方虽然合法在 int 范围内，但不合法的情况会炸。

巴特西

@codeforces - 506C@ Mr. Kitayuta vs. Bamboos

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章