「CF442C」 Artem and Array

题目链接

\(Solution\)

观察发现如果一个数两边都比他大，删掉他可以保证最优，这个应该是显然的。这个东西用单调栈维护一下，最后剩下的就是个单调递减或单调递增的数列，从小到大排个序取前面\(n-2\)个,\(n\)为数列长度

\(Code\)

#include<bits/stdc++.h>

#define int long long

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

using namespace std;

int read(){

	int x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

	return f*x;

}

const int N=5e5+10;

stack<int> s;

int a[N];

main(){

	int n=read(),ans=0,x,y,tot=0;

	for(int i=1;i<=n;i++){

		a[i]=read();

		while(s.size()>=2){

			x=s.top(),s.pop(),y=s.top();

			if(y>=x&&x<=a[i]) ans+=min(a[i],y);

			else {s.push(x);break;}

		}

		s.push(a[i]);

	}

	while(!s.empty())

		a[++tot]=s.top(),s.pop();

	sort(a+1,a+1+tot);

	for(int i=1;i<tot-1;i++)

		ans+=a[i];

	printf("%lld",ans);

	return 0;

}

巴特西

「CF442C」 Artem and Array

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章