Codeforces Round #253 DIV1 C 贪心_html/css_WEB-ITnose-html教程-PHP中文网

Codeforces Round #253 DIV1 C 贪心_html/css_WEB-ITnose

php中文网

发布： 2016-06-24 12:00:57

原创

1329人浏览过

http://codeforces.com/contest/442/problem/c

题意很easy，基本上肯定有坑坑洼洼的样子，看题目案例，从第三个跟第二个没有凹的案例来看的话，多写几个以及多画画过程稍微推一下就会发现，除了最大的两个数以外都可以得到，然后就是凹的情况了，凹的情况肯定是唯一的，把中间的数除去得到一个值，但是凹凸有结合该怎么办，猜一把先把凹的单独一个个给解决了，产生没有凹的序列再处理，然后刚好对于第一个案例进行测试，发现答案正确，于是就这么贪心的敲了一个

对于凹的情况可以使用栈来处理，处理完对于没有凹的情况直接排序除了最大的两个数以外其它可以都取了

蓝心千询

蓝心千询是vivo推出的一个多功能AI智能助手

查看详情

立即学习“前端免费学习笔记（深入）”；

#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define eps 1e-8const int inf = 0xfffffff;const ll INF = 1ll<<61;using namespace std;//vector<pair<int,int> > G;//typedef pair<int,int > P;//vector<pair<int,int> > ::iterator iter;////map<ll,int >mp;//map<ll,int >::iterator p;int n;int num[1000000 + 5];stack<int >	s;ll ans; void init() {	memset(num,0,sizeof(num));	while(!s.empty())s.pop();	ans = 0ll;}bool input() {	while(scanf("%d",&n) == 1) {		for(int i=0;i<n;i++)			scanf("%d",&num[i]);		return false;	}	return  true;}void cal() {	bool flag = false;	s.push(num[0]);	for(int i=1;i<n;i++) {		if(num[i] <= s.top()) {s.push(num[i]);flag = true;continue;}		if(num[i] >= s.top() && flag) {			s.pop();			ans += min(num[i],s.top());			if(num[i] <= s.top())flag = true;			else  {				while(true) {					int tmp = s.top();					s.pop();					if(s.empty()) {						s.push(tmp);						break;					}					if(tmp > s.top() || num[i] < tmp) {						s.push(tmp);						break;					}					if(num[i] >= tmp)ans += min(s.top(),num[i]);				}			}			if(num[i] <= s.top())flag = true;			else flag = false;			s.push(num[i]);			continue;		}		s.push(num[i]);	}	memset(num,0,sizeof(num));	int cnt = 0;	while(!s.empty()) {		num[cnt++] = s.top();		s.pop();	}	sort(num,num+cnt);	for(int i=0;i<cnt-2;i++)		ans += num[i];}void output() {	printf("%I64d\n",ans);}int main() {	while(true) {		init();		if(input())return 0;		cal();		output();	} }

登录后复制

立即学习“前端免费学习笔记（深入）”；