CF Gym 100917D dir -C

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

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

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

线性查找的时间不忍直视，所以这道题目实际上是查询区间最值，线段树可解，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;
}