求问为什么正确
查看原帖
求问为什么正确
1037830
Ooj_bai楼主2024/7/24 19:30
#include<bits/stdc++.h>
#define red(i,n) for(int i=1;i<=n;i++) 
#define int long long 
using namespace std;
struct node{
	int num,a;
}sta[1000005];
int n,top,minn=1e9,num;
int a[1000005],ans[500005];
int l[1000005],r[1000005];
int D2[1000005];
signed main(){
	cin>>n;
	red(i,n)cin>>a[i],a[i+n]=a[i];
	red(i,n){
		if(a[i]<minn){
			minn=a[i];
			num=i;
		}
	}
	red(i,2*n){
		while(a[i]<=sta[top].a&&top>=1)top--;
		l[i]=sta[top].num;
		sta[++top]={i,a[i]};
	}
	memset(sta,0,sizeof sta);top=0;
	for(int i=2*n;i>=1;i--){
		while(a[i]<sta[top].a&&top>=1)top--;
		r[i]=sta[top].num;
		sta[++top]={i,a[i]};
	}
	for(int i=num;i<num+n;i++){
		int L=l[i]+1,R=r[i]-1;
		D2[1]+=a[i];D2[i-L+2]-=a[i];
		D2[R-i+2]-=a[i];D2[R-L+3]+=a[i];
	}
	red(i,2*n)D2[i]+=D2[i-1];
	red(i,2*n)D2[i]+=D2[i-1];
	for(int i=2;i<=n+1;i++){
		cout<<D2[i]<<'\n';
	}
	return 0;
}

在我最初的代码(如上)中,答案比标准答案在尾部差一个等差数列。同时,我发现其公差及位置与数列中最小的数及其下标(即代码中 minnminn 与 numnum )有关。
于是我脑子一热加了

for(int i=1;i<=n;i++){
	D2[num+i]+=i*minn;
}   

然后就过了。
Q:如题,为什么?

2024/7/24 19:30
加载中...