首页 > 其他 > 详细

CF140CNew Year Snowmen

时间:2019-10-02 20:31:26      阅读:137      评论:0      收藏:0      [点我收藏+]

CF140C

题目大意:堆雪人,需要三个大小不同的雪球,现有\(n\)个给定大小的雪球,问最多堆多少个雪人

一个很明显的思路是把每种雪球出现的个数记录下来,然后直接扔到大根堆里面,每次选择剩下出现次数最多的三个堆成一个雪人,可以证明,这样一定不会比选择小的更劣

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#define LL long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 3;
int a[N];
int n;
int s[5];
priority_queue <pii> q; 
struct node{
    int x,y,z;  
}qq[N];
inline int read(){
    int v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;
}
int main(){
    n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    sort(a + 1,a + n + 1);
    int res = 1;
    for(int i = 1;i <= n;++i){
        if(a[i] == a[i + 1]) res++;
        else{
            q.push(mk(res,a[i]));
            res = 1;
        }
    }int ans = 0;
    while(q.size() >= 3){
        pii k1 = q.top();q.pop();
        pii k2 = q.top();q.pop();
        pii k3 = q.top();q.pop();
        ans++;
        s[1] = k1.se,s[2] = k2.se,s[3] = k3.se;
        sort(s + 1,s + 4);
        qq[ans] = (node){s[3],s[2],s[1]};
        k1.fi--,k2.fi--,k3.fi--;
        if(k1.fi) q.push(k1);
        if(k2.fi) q.push(k2);
        if(k3.fi) q.push(k3);
    }
    printf("%d\n",ans);
    for(int i = 1;i <= ans;++i) printf("%d %d %d\n",qq[i].x,qq[i].y,qq[i].z);
    return 0;
}

CF140CNew Year Snowmen

原文:https://www.cnblogs.com/wyxdrqc/p/11617947.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!