MYF

2016弱校连萌Round 1d dir -C

题目链接

dir -C

方法: sparse table解决RMQ问题

题目分析

题目大意

给定n个文件的文件名长度ai,该行长度w,文件竖着输出,问,最少需要多少行才可以容纳所有的文件。

解析

一开始没看清楚题,以为文件是横着排的,别人说这题是RMQ的时候看完题还是没反应过来。后来理解了一下题意,发现是竖着来的。所以,只要从小到大枚举每行的文件数量即可,找到第一个可以容纳这么多文件的宽度。使用Sparse Table或者线段树来处理应该都可以,扫出每个连续区间的最大值,然后相加,小于等于w时输出即可~注意要用long long,否则会炸。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
#include "cmath"
using namespace std;
const int maxn = 150005;//数据量
const int NVB = 33;//对于整型而言,其值不会超过2^32,因此第二维大小为33已经足够
int mx[maxn][NVB],mn[maxn][NVB];
void init(int data[],int n){
/*data下标从1开始*/
int k = log2(n);
for(int i=1; i<=n; i++)
mx[i][0] = mn[i][0] = data[i];
for(int j=1; j<=k; j++){
for(int i=1; i+(1<<j)-1<=n; i++){
mx[i][j] = max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
mn[i][j] = min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r,int flag){
int k = log2(r-l+1);
if(flag) return max(mx[l][k],mx[r-(1<<k)+1][k]);
else return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
int main(){
int n,w;
int a[maxn];
scanf("%d%d",&n,&w);
for (int i=1; i<=n; i++) {
scanf("%d",a+i);
a[i]++;
}
init(a, n);
for (int i=1; i<=n; i++) {
long long ans=-1;
for (int j=1; j<=n; j+=i) {
ans+=query(j, min(j+i-1,n), 1);
}
if (ans<=w) {
printf("%d\n",i);
return 0;
}
}
}