本题一开始想的是用f[i][j]表示从i开始长度为2^j的和,然后每次查询的时候利用倍增去快速找到某一段的最右边。结果超时了,后来想了下,万一卡一个n段的数据,就挂了。而且这样倍增还不如直接O(1)预处理每个点到下一段的距离来得快。
题意:
给你一个长为n的序列a和一个常数k
有m次询问,每次查询一个区间[l,r]内所有数最少分成多少个连续段,使得每段的和都 <= k
如果这一次查询无解,输出"Chtholly"
思路:
用f[i][j]表示从i出发走了2^j段的最远的点的下一个点。
显然有:f[i][j]=f[f[i][j-1]][j-1]
对于f[i][0]来说,可以O(n)预处理或者二分查找前缀和数组。
然后对每次询问去倍增查找就好了。
对于无解的情况其实就是看[l,r]中是否存在一个数字超过K的。那么预处理一下maxi[i]数组记录前i个数里面超过k的个数,做差判断就可以。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,m,k,a[1000040],maxi[1000040]; ll f[1000040][22],sum[1000050]; void init(){ for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; for(int i=1;i<=n;i++){ maxi[i]=maxi[i-1]+(a[i]>k); } } int erfen(int l){ int x=lower_bound(sum+1,sum+1+n,sum[l-1]+k+1)-sum; return x; } void ST(){ for(int i=1;i<=n;i++)f[i][0]=erfen(i); for(int j=1;j<=20;j++){ for(int i=1;i<=n;i++){ f[i][j]=f[f[i][j-1]][j-1]; } } } int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++)scanf("%d",&a[i]); init(); ST(); while(m--){ int l,r,ans=1; scanf("%d%d",&l,&r); if(maxi[r]-maxi[l-1]>0)cout<<"Chtholly"<<endl; else { for(int j=20;j>=0;j--){ if(f[l][j]&&f[l][j]<=r){ l=f[l][j]; ans+=(1<<j); } } printf("%d\n",ans); } } return 0; }
一点疑问:
我一开始想用f[i][j]表示从i走过2^j段的最远距离的点(不是下一个)。这样写感觉也是可以的,但是总是只能过30%,对倍增还是不熟啊。希望有大神能指点一二。