P11822 题解

在求解单个问题时，我们采用以下策略：从后往前考虑。对于一个

i

，如果其能成为一个分段点（即以其为左端点的段和大于其后面的所有段），那么就直接令其成为分段点。

证明：首先如果不令其成为分段点，那么其余方案的字典序一定会变小。而令其成为分段点时，将左边所有数分成一段一定是个合法方案。

暴力模拟本策略就可以达到

O(n^2)

复杂度，得分 50pts。

直觉地想，向后 push_back 一个数之后，合法方案改变的不会很多（否则重新计算方案对应的答案的时间复杂度就是

O(n^2)

了），且改变的一定是一段后缀。于是我们可以从最后一个数开始，一直使用二分的形式确定下一个分段点。如果有两个新方案的相邻的分段点在旧方案中依然相邻，那么前面的所有分段都不会变，应该停止。如果已经二分到以

0

作为分段点，那么也应该停止。

时间复杂度不会证，但是跑得挺快。赛时在 std::stack 的大常数加持下可以获得

90

分。赛后一把这玩意重写就过了。

CPP

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=1e5;

template<class T>
struct Stack{
	int tail=0;
	T in[maxn+5];
	
	T top(){
		return in[tail];
	}
	
	bool empty(){
		return tail==0;
	}
	
	void push(T x){
		in[++tail]=x;
	}
	
	void pop(){
		tail--;
	}
	
	int size(){
		return tail;
	}
};

int a[maxn+5],sum[maxn+5];
Stack<pair<int,int>> sta1;
Stack<int> sta2;

bool able(int l,int r,int ge){
	if(l==0){
		return 1;
	}
	return sum[r-1]-sum[l-1]>ge;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin>>n;
	sum[0]=a[0]=1e18;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	sta1.push(make_pair(0,0));
	for(int i=1;i<=n;i++){
		sta2.push(i);
		int lstv=a[i],lstpop=i-1;
		bool nochance=0;
		while(1){
			auto tmp=sta1.top();
			if(!able(tmp.first,sta2.top(),lstv)){
				lstpop=sta1.top().first-1;
				sta1.pop();
				nochance=0;
			}
			else{
				int l=tmp.first,r=lstpop;
				while(l<r){
					int mid=((l+r)>>1)+1;
					if(able(mid,sta2.top(),lstv)){
						l=mid;
					}
					else{
						r=mid-1;
					}
				}
				if(l==tmp.first){
					if(nochance||l==0)
						break;
					else{
						lstv=sum[sta2.top()-1]-sum[tmp.first-1];
						sta2.push(tmp.first);
						sta1.pop();
						nochance=1;
					}
				}
				else{
					lstv=sum[sta2.top()-1]-sum[l-1];
					sta2.push(l);
					nochance=0;
				}
			}
		}
		while(!sta2.empty()){
			sta1.push(make_pair(sta2.top(),sta1.top().second+sta1.size()*sta2.top()));
			sta2.pop();
		}
		cout<<sta1.top().second+(i+1)*sta1.size()<<" ";
	}
}

文章操作

相关推荐

评论

P11822 题解