C++14(g++5.4) 解法, 执行用时: 263ms, 内存消耗: 29412K, 提交时间: 2019-08-22 22:17:36

#include<bits/stdc++.h>
#define M 100005
#define ll long long
using namespace std;
int T,fa[M][20],pos[M][20],a[M],n,v;
ll sum[M];
void Init() {
	for(int j=1; (1<<j)<=n; j++) {
		for(int i=1; i+(1<<j)-1<=n; i++) {
			int x=i+(1<<j-1);
			if(fa[i][j-1]>fa[x][j-1])fa[i][j]=fa[i][j-1],pos[i][j]=pos[i][j-1];
			else fa[i][j]=fa[x][j-1],pos[i][j]=pos[x][j-1];
		}
	}
}
int lg2[M],id;
int get(int l,int r) {
	int k=lg2[r-l+1];
	if(fa[l][k]>fa[r-(1<<k)+1][k])return pos[l][k];
	else return pos[r-(1<<k)+1][k];
}
struct node {
	ll l,r;
	bool operator<(const node&_)const {
		if(l!=_.l)return l<_.l;
		return r<_.r;
	}
} Q[18*M];
void fenzhi(int l,int r) {
	if(l>r)return;
	ll now=sum[r]-sum[l-1];
	int k=get(l,r);
	Q[++id]=(node)<%ceil(1.0*a[k]/v),now%>;
	fenzhi(l,k-1),fenzhi(k+1,r);
}
void solve() {
	sort(Q+1,Q+id+1);
//	for(int i=1;i<=id;i++)printf("%lld %lld\n",Q[i].l,Q[i].r);
	ll l=0,ans=0;//之前最远延伸到的地方
	for(int i=1; i<=id; i++) {
		if(Q[i].r<=l)continue;
		if(Q[i].l>l)ans=(ans+Q[i].r-Q[i].l+1);
		else ans=(ans+Q[i].r-l+1);
		l=Q[i].r+1;
	}
	printf("%lld\n",ans);
}
int main() {
	lg2[1]=0;
	for(int i=2; i<M; i++)lg2[i]=lg2[i>>1]+1;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&v);
		id=0,sum[0]=0;
		for(int i=1; i<=n; i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
		for(int i=1; i<=n; i++)fa[i][0]=a[i],pos[i][0]=i;
		Init();
//		for(int i=1;i<=n;i++,puts(""))for(int j=0;j<=18;j++)printf("%d %d %d\n",i,i+(1<<j)-1,fa[i][j]); 
		fenzhi(1,n);
		solve();
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 164ms, 内存消耗: 872K, 提交时间: 2019-09-30 16:22:26

#include<bits/stdc++.h>
using namespace std;
#define M 100005
#define ll long long
int a[M],n,v;
ll cl(ll l,ll r){
	ll sum=0,ans1=0,ans2=1e18;
	for(int i=1,pr=1;i<=n;++i){
		sum+=a[i];
		while(sum>=r&&pr<=i)sum-=a[pr],pr++;
		if(pr<=i){
			if(sum>=l)ans2=min(ans2,sum);
			else ans1=max(ans1,sum);
		}
	}
	if(ans2<r)return ans2;
	return ans1;
}
void solve(){
	scanf("%d%d",&n,&v);ll sum=0,ans=0;
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),sum+=a[i];
	ll l=(sum+v-1)/v-1,r=sum;ans+=sum-l;
	while(r){
		ll w=cl(l,r);
		if(w==0)break;
		ans+=min(w,l)-((w+v-1)/v-1);r=w;
		l=(w+v-1)/v-1;
	}
	printf("%lld\n",ans);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--)solve();
	return 0;
}