正題

題目鏈接:https://www.luogu.com.cn/problem/CF140C

---

題目大意

$n$個(gè)雪球，一個(gè)雪人需要用$3$個(gè)不同大小的雪球堆起，求最多雪人。

---

解題思路

我們每次拿相同雪球中最多的三個(gè)來堆即可，用優(yōu)先隊(duì)列維護(hù)。

時(shí)間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define mp(x,y) make_pair(x,y) using namespace std; const int N=1e5+10; int n,a[N],ans,b1[N],b2[N],b3[N]; priority_queue<pair<int,int> > q; int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n);int cnt=0;for(int i=1;i<=n;i++){cnt++;if(a[i]!=a[i+1])q.push(mp(cnt,a[i])),cnt=0;}while(1){if(q.empty())break;pair<int,int> x=q.top();q.pop();if(q.empty())break;pair<int,int> y=q.top();q.pop();if(q.empty())break;pair<int,int> z=q.top();q.pop();ans++;b1[ans]=x.second;b2[ans]=y.second;b3[ans]=z.second;if(x.first>1)q.push(mp(x.first-1,x.second));if(y.first>1)q.push(mp(y.first-1,y.second));if(z.first>1)q.push(mp(z.first-1,z.second));}printf("%d\n",ans);for(int i=1;i<=ans;i++){if(b1[i]<b2[i])swap(b1[i],b2[i]);if(b1[i]<b3[i])swap(b1[i],b3[i]);if(b2[i]<b3[i])swap(b2[i],b3[i]);printf("%d %d %d\n",b1[i],b2[i],b3[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF140C-New Year Snowmen【优先队列】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。