题目链接：http://codeforces.com/gym/100917/problem/D
题目大意是，给 个文件名的长度，按照类似 dir -C 命令的形式，从上到下，从左到右排列这些文件，给定一个固定的窗口宽度 （每一列最长文件名之和不可超过 ），求最少需要打印多少行能够满足不超过 的条件（列与列之间用空格隔开）
此题很容易想到从小到大穷举行数，只要找到满足条件的情况就可退出，那么实际上主要的时间就耗费在检查是否满足条件这一过程中。暴力解法是线性查找每一列文件名长度最大值 ，最后直接比较 与 的大小。
线性查找的时间不忍直视，所以这道题目实际上是查询区间最值，线段树可解，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; | |
} |
