codeforces100917dir -C

r囧r小猫 2022-07-16 03:41 103阅读 0赞

codeforces100917dir -C 题目链接：[http://codeforces.com/gym/100917/problem/D][http_codeforces.com_gym_100917_problem_D]

题目描述：

D. dir -C

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Famous Berland coder and IT manager Linus Gates announced his next proprietary open-source system "Winux 10.04 LTS"

In this system command "dir -C" prints list of all files in the current catalog in multicolumn mode.

Lets define the multicolumn mode for number of lines *l*. Assume that filenames are already sorted lexicographically.

*  We split list of filenames into several continuous blocks such as all blocks except for maybe last one consist of *l* filenames, and last block consists of no more than *l* filenames, then blocks are printed as columns.
 *  Width of each column *w**i* is defined as maximal length of the filename in appropriate block.
 *  Columns are separated by 1 × *l* column of spaces.
 *  So, width of the output is calculated as ![110abe3b7ae4ea589088f2ff34c48185d9f73d2f.png][], i.e. sum of widths of each column plus number of columns minus one.

Example of multi-column output:

a       accd e t
    aba     b    f wtrt
    abacaba db   k

In the example above width of output is equal to 19.

"dir -C" command selects minimal *l*, such that width of the output does not exceed width of screen *w*.

Given information about filename lengths and width of screen, calculate number of lines *l* printed by "dir -C" command.

Input

First line of the input contains two integers *n* and *w* — number of files in the list and width of screen (1 ≤ *n* ≤ 105, 1 ≤ *w* ≤ 109).

Second line contains *n* integers *f**i* — lengths of filenames. *i*\-th of those integers represents length of *i*\-th filename in the lexicographically ordered list (1 ≤ *f**i* ≤ *w*).

Output

Print one integer — number of lines *l*, printed by "dir -C" command.

Examples

input

11 20
    1 3 7 4 1 2 1 1 1 1 4

output

题目大意和分析：

每一行都有最大权重，为了在最少的行中打印输出全部的文件名称，所以采用在某些区间中求解最大值的方法，即采用RMQ（区间最值询问）的方法，对每个需要划分的区间都进行打表，则在询问时则是O(1)的复杂度，比线段树实现要快，之后的区间则需要暴力进行查找。

代码实现：

#include <stdio.h>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #define N 500100
    
    using namespace std;
    
    long long sa[N][30];
    long long sum;
    void RMQ_Init(long long n)
    {
        long long e,i,j;
        sum=0;
        memset(sa,0,sizeof(sa));
        for(i=1; i<=n; i++)
        {
            scanf("%lld",&e);
            sum+=e;
            sa[i][0]=e;//DP初始化呢
        }
        //次处求出2^p<=n时的p，即从i开始往后的2^j的数
        long long p=(long long)(log((double)n)/log(2.0));
        for(j=1; j<=p; j++)
            for(i=1; i+(1<<j)-1<=n; i++)
            {
                sa[i][j]=max(sa[i][j-1],sa[i+(1<<(j-1))][j-1]);
            }
    }
    
    long long RMQ(long long a,long long b)
    {
        long long p=(long long)(log((double)(b-a+1))/log(2.0));
        long long maxh=max(sa[a][p],sa[b-(1<<p)+1][p]);
        return maxh;
    }
    
    int main()
    {
        long long n,w;
        while(scanf("%lld%lld",&n,&w)!=EOF)
        {
            long long flag=0;
            RMQ_Init(n);
            for(long long j=1; j<=n; j++)
            {
                long long ans=0;
                long long a=n%j;
                for(long long i=1; i<=n-a; i+=j)
                {
                    ans=ans+RMQ(i,i+j-1)+1;
                }
                if(a)
                {
                    ans=ans+RMQ(n-a+1,n)+1;
                }
                ans--;
                if(ans<=w)
                {
                    cout<<j<<endl;
                    flag=1;
                    break;
                }
                if(flag)
                    break;
            }
        }
        return 0;
    }

[http_codeforces.com_gym_100917_problem_D]: http://codeforces.com/gym/100917/problem/D
[110abe3b7ae4ea589088f2ff34c48185d9f73d2f.png]: /images/20220716/994693bafac94018afe91b129806717b.png