题目链接: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; | |
} |