2016弱校连萌Round 1d dir -C

题目链接

dir -C

方法： sparse table解决RMQ问题

题目分析

题目大意

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

解析

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

代码

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