C++11(clang++ 3.9) 解法, 执行用时: 24ms, 内存消耗: 2964K, 提交时间: 2020-09-07 06:52:37

#include <bits/stdc++.h>
typedef long long ll;

inline void read(ll&x){
	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();
}

const int N=101000,bs=1e5;
int n,tp;

struct vec{
	int x;ll y;
	inline vec(){}
	inline vec(const int&X,const ll&Y):x(X),y(Y){}
	friend inline vec operator - (const vec&A,const vec&B) {return vec(A.x-B.x,A.y-B.y);}
	friend inline ll operator * (const vec&A,const vec&B) {return A.x*B.y-A.y*B.x;}
}p,st[N];

void push(vec p){
	while(tp&&(p-st[tp])*(st[tp]-st[tp-1])<=0)--tp;
	st[++tp]=p;
}

int main(){
	scanf("%d",&n);vec p;
	for(int i=1;i<=n;++i)p.x=i,read(p.y),p.y*=bs,push(p);
	push(vec(n+1,0));
	for(int i=1,j=0;i<=n;++i){
		while(j<tp&&st[j].x<i)++j;
		if(st[j].x==i)printf("%lld\n",st[j].y);
		else printf("%lld\n",((st[j].x-i)*st[j-1].y+(i-st[j-1].x)*st[j].y)/(st[j].x-st[j-1].x));
	}return 0;
}

C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 4364K, 提交时间: 2020-09-07 09:19:19

#include <bits/stdc++.h>
const int N=1e5;
int n,cnt;

struct node{
	int x;
	long long y;
	node(int a=0,long long b=0){
		this->x=a;
		this->y=b;
	}
	node operator - (const node &a) {return node(x-a.x,y-a.y);}
	long long operator * (const node &a) {return x*a.y-y*a.x;}
}jia,s[N+10];

void push(node nw){
	while(cnt&&(nw-s[cnt])*(s[cnt]-s[cnt-1])<=0) --cnt;
	s[++cnt]=nw;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&jia.y),jia.x=i,jia.y*=N,push(jia);
	push(node(n+1,0));
	for(int i=1,j=0;i<=n;++i){
		while(j<cnt&&s[j].x<i) ++j;
		if(s[j].x==i) printf("%lld\n",s[j].y);
		else printf("%lld\n",((s[j].x-i)*s[j-1].y+(i-s[j-1].x)*s[j].y)/(s[j].x-s[j-1].x));
	}return 0;
}