#单调队列#洛谷 1090 SSL 1040 VIJOS 1097 CODEVS 1063 合并果子

本文主要是介绍#单调队列#洛谷 1090 SSL 1040 VIJOS 1097 CODEVS 1063 合并果子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目及O（$nlo{g}_{2}n$）做法

---

分析

其实我们也可以用O（n）来做，首先来个桶排。
再用一个单调队列存下两个最小值，不断更新。

---

代码

#include <cstdio>
#include <cctype>
using namespace std;
short t[20001],l,r,min[2],n,head; int a[30001],ans;
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int main(){n=in(); for (int i=1;i<=n;i++) t[in()]++;n=0; for (int i=1;i<=20000;i++) for (int j=1;j<=t[i];j++) a[++n]=i;l=1; r=2*n+1; head=2*n; for (int i=1;i<n;i++){for (int j=0;j<2;j++){if (a[l]<=a[r]&&l<=n||!a[r]) min[j]=l++;//最后空了或者是最小的else if (r<=head) min[j]=r++;//没用过else min[j]=l++;//用过了}ans+=a[++head]=a[min[0]]+a[min[1]];//最小值并插入}return !printf("%d",ans);
}

这篇关于#单调队列#洛谷 1090 SSL 1040 VIJOS 1097 CODEVS 1063 合并果子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---