欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

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

程序员文章站 2022-05-15 10:15:22
...
http://codeforces.com/contest/442/problem/C

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

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


#include#include#include#include#include#include#include#include#include#include#include#include#include#define ll long long#define eps 1e-8const int inf = 0xfffffff;const ll INF = 1ll > G;//typedef pair P;//vector > ::iterator iter;////mapmp;//map::iterator p;int n;int num[1000000 + 5];stack	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= s.top() && flag) {			s.pop();			ans += min(num[i],s.top());			if(num[i]  s.top() || num[i] = tmp)ans += min(s.top(),num[i]);				}			}			if(num[i]