题目链接:http://codeforces.com/gym/100917/problem/D

题目大意是,给 nn 个文件名的长度,按照类似 dir -C 命令的形式,从上到下,从左到右排列这些文件,给定一个固定的窗口宽度 ww(每一列最长文件名之和不可超过 ww),求最少需要打印多少行能够满足不超过 ww 的条件(列与列之间用空格隔开)

此题很容易想到从小到大穷举行数,只要找到满足条件的情况就可退出,那么实际上主要的时间就耗费在检查是否满足条件这一过程中。暴力解法是线性查找每一列文件名长度最大值 MaxwiMaxw_i,最后直接比较 (Maxwi+1)1\sum{(Maxw_i + 1)} - 1ww 的大小。

线性查找的时间不忍直视,所以这道题目实际上是查询区间最值,线段树可解,RMQ 可搞,代码如下:

#include <cstdio>
#include <cmath>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define N 110000
using namespace std;
int n, w, t, p, f[N][20];
inline void RMQ() {
	for (int j = 0; j < 18; j++)
		for (int i = 1; i <= n; i++)
			if ((t = (1 << j) + i) <= n)
				f[i][j + 1] = MAX(f[i][j], f[t][j]);
}
inline int query(int x, int y) {
	int k = log(y- x + 1) / log(2);
	return MAX(f[x][k], f[y - (1 << k) + 1][k]);
}
int main() {
	scanf("%d%d", &n, &w);
	for (int i = 1; i <= n; i++)
		scanf("%d", &f[i][0]);
	RMQ();
	long long s; int i;
	for (i = 1; i <=n; i++) {
		s = 0;
		for (p = 1; p <= n; p += i) {
			t = p + i - 1;
			if (t > n) t = n;
			s += query(p, t) + 1;
		}
		if (s - 1 <= w) break ;
	}
	printf("%d\n", i);
	return 0;
}
更新于 阅读次数