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;
}