codeforces gym100917 dir -C 枚举+st表

https://codeforces.com/gym/100917/problem/D

题目大意：有$n$个目录名字符串，长度为$a[1]-a[n]$，屏幕宽为$w$，现在要按照已经给的目录序列顺序的放置，每一列要放$x$个，最后一列可以放$<=x$个，列与列之间的距离为$1$，每一行所占宽度要$<=w$，问可以放置完全部目录的最小的$x$的值(也即最小的行数)。

思路：一开始想的是二分行数，后来发现并不满足单调性，比如这组数据：$$n=9w=150001,1,1,7000,1,1,1,7000,7000$$
在$n=3$的时候满足题意，而在$n=4$的时候却不满足题意。因此我们只能从$1$枚举到$n$，但是暴力计算最大值的话是会超时的，如果能够在$O(1)$的时间内计算出区间最大值，那么可以把复杂度降到$O(nlgn)$，因为$n+n/2+n/3+\dots \dots +1=nlgn$。那么利用$st$表就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn=1e5+5;
int bs[maxn];
int a[maxn];
int n,w;
int st[maxn][30];
inline void init()
{
int MAX=bs[n];
for(int i=1;i<=n;i++)
st[i][0]=a[i];//2^0-1=0 即st[i][j]维护的是区间[i,i]的值 即本身
for(int j=1;j<=MAX;j++)//外层循环是j
{
for(int i=1;i<=n;i++)
{
if(i+(1<<j)-1<=n)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
else
break;
}
}
}
inline int query(int l,int r)
{
int len=r-l+1;
int t=bs[len];	//2^(log2(a))>a/2
return max(st[l][t],st[r-(1<<t)+1][t]);
}
int main()
{
scanf("%d%d",&n,&w);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
bs[i]=log2(i);
init();
ll sum=0;
int r=0;
for(int i=1;i<=n;i++)
{
sum=0;
for(int j=1;j<=n;j+=i)
{
r=min(j+i-1,n);
sum+=query(j,r)+1;
if(sum>=w+2)
break;
}
--sum;
if(sum<=w)
{
printf("%dn",i);
break;
}
}
return 0;
}

最后

以上就是忐忑小馒头最近收集整理的关于codeforces gym100917 dir -C 枚举+st表的全部内容，更多相关codeforces内容请搜索靠谱客的其他文章。