codeforces100917dir -C

56 阅读 0 评论 37 点赞

我是靠谱客的博主忧伤音响，最近开发中收集的这篇文章主要介绍codeforces100917dir -C，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

题目描述：

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 wi 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 $\text{[math]}$ , 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 fi — lengths of filenames. i-th of those integers represents length of i-th filename in the lexicographically ordered list (1 ≤ fi ≤ 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
3

题目大意和分析：

每一行都有最大权重，为了在最少的行中打印输出全部的文件名称，所以采用在某些区间中求解最大值的方法，即采用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;
}