即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

【映射 && 优先队列】CodeForces – 140C New Year Snowmen

编程语言 bbbbswbq 13℃ 0评论

Problem Description

输入n,然后给你n个雪球半径,让你堆雪人,每个雪人由三个球组成,而且球不能一样,问你最多能堆出几个。

代码:用map求出每个相同的雪球出现了几次,然后存入优先队列(按出现次数多到少存),每次取出最多的三种小球,组成雪人,这样才能保证雪人最多。

#include
using namespace std;
struct node
{
    int data, num;//雪球大小,雪球数量
    bool operator < (const node &b) const {
        if(num == b.num) return data < b.data;
        else return num < b.num;
    }
};
int ans[40000][3];//用来存答案
int main()
{
    int n, i, j, num1;
    while(~scanf("%d", &n))
    {
        map<int,int> s;//map
        map<int,int>::iterator it;
        priority_queue q;//出现次数多优先出来
        for(i = 0; i < n; i++)
        {
            scanf("%d", &num1);
            s[num1]++;//用map记录出现了几次
        }
        for(it = s.begin(); it != s.end(); it++)
        {
            q.push((node){it->first, it->second});//存入到优先队列
        }
        int top = 0;
        node a, b, c;//分别用于取出三个雪人球
        while(!q.empty())
        {
            a = q.top();//取出
            ans[top][0] = a.data;//存入答案
            q.pop();//出列
            a.num--;//雪人球数--

            if(q.empty()) break;//判断是否空,空了就没法取了
            b = q.top();
            ans[top][1] = b.data;
            q.pop();
            b.num--;

            if(q.empty()) break;
            c = q.top();
            ans[top][2] = c.data;
            q.pop();
            c.num--;

            sort(ans[top], ans[top] + 3);//给他们排序
            top++;
            if(a.num) q.push(a);//还有雪球,存入
            if(b.num) q.push(b);
            if(c.num) q.push(c);
        }
        printf("%d\n", top);
        for(i = 0; i < top; i++)
        {
            printf("%d %d %d\n", ans[i][2], ans[i][1], ans[i][0]);
        }
    }
    return 0;
}

转载请注明:CodingBlog » 【映射 && 优先队列】CodeForces – 140C New Year Snowmen

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情