首页 > 试题广场 >

CodeForces 140C New Year Snowm

[编程题]CodeForces 140C New Year Snowm

热度指数：74 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

As meticulous Gerald sets the table and caring Alexander sends the postcards, Sergey makes snowmen. Each showman should consist of three snowballs: a big one, a medium one and a small one. Sergey's twins help him: they've already made n snowballs with radii equal to r ₁ , r ₂ , ..., r _n . To make a snowman, one needs any three snowballs whose radii are pairwise different. For example, the balls with radii 1, 2 and 3 can be used to make a snowman but 2, 2, 3 or 2, 2, 2 cannot. Help Sergey and his twins to determine what maximum number of snowmen they can make from those snowballs.

输入描述:

The first line contains integer n (1 ≤ n ≤ 10⁵) — the number of snowballs. The next line contains n integers — the balls' radii r₁, r₂, ..., r_n (1 ≤ r_i ≤ 10⁹). The balls' radii can coincide.

输出描述:

Print on the first line a single number k — the maximum number of the snowmen. Next k lines should contain the snowmen's descriptions. The description of each snowman should consist of three space-separated numbers — the big ball's radius, the medium ball's radius and the small ball's radius. It is allowed to print the snowmen in any order. If there are several solutions, print any of them.

示例1

输入

7<br />1 2 3 4 5 6 7<br />3<br />2 2 3<br />

输出

2<br />3 2 1<br />6 5 4<br />0<br />

算法知识视频讲解

C/C++

梦樱羽

很明显是贪心，不过贪心策略有待斟酌。

一开始我想当然的把数据按大小排序后从小到大贪心，结果就Wa了，很容易找到反例：

1 2 3 4 4 4 5 5 5

如果从小到大贪，那么答案为1，不过这组数据眼睛看看答案都应该是3。造成这种情况的原因是我把数量少的先贪掉了，很多数量多的没得贪。因此贪心策略应该先贪数量多的。

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)

#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl

#define LOWBIT(x) ((x)&(-x))

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

#define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
#define msM(a) memset(a,-1,sizeof(a))

#define pii pair<int,int> 
#define piii pair<pair<int,int>,int> 
#define mp make_pair
#define pb push_back
#define fi first
#define se second

inline int gc(){
    static const int BUF = 1e7;
    static char buf[BUF], *bg = buf + BUF, *ed = bg;
    
    if(bg == ed) fread(bg = buf, 1, BUF, stdin);
    return *bg++;
} 

inline int ri(){
    int x = 0, f = 1, c = gc();
    for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
    for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
    return x*f;
}

typedef long long LL;
typedef unsigned long long uLL;
const int inf = 1e9 + 9;
const LL mod = 1e9 + 7;
const int maxN = 1e5 + 7;

struct Node{
    int value, amount = 0;
    
    inline bool operator < (const Node &x) const {
        return amount < x.amount;
    }
};

int n, nlen, ans;
Node nodes[maxN];
unordered_map< int, int > mii;
priority_queue< Node > maxH;
int Ans[maxN][3];

int main(){
    while(cin >> n) {
        mii.clear();
        nlen = 0;
        rep(i, n) {
            int t;
            scanf("%d", &t);
            if(mii.find(t) != mii.end()) {
                ++nodes[mii[t]].amount;
            }
            else {
                mii[t] = nlen;
                nodes[nlen].value = t;
                nodes[nlen++].amount = 1;
            }
        }
        
        while(!maxH.empty()) maxH.pop();
        rep(i, nlen) maxH.push(nodes[i]);
        
        ans = 0;
        
        while(maxH.size() >= 3) {
            Node a = maxH.top();
            maxH.pop();
            Node b = maxH.top();
            maxH.pop();
            Node c = maxH.top();
            maxH.pop();
            
            int x = min(min(a.value, b.value), c.value);
            int z = max(max(a.value, b.value), c.value);
            int y = a.value + b.value + c.value - x - z;
            Ans[ans][0] = x;
            Ans[ans][1] = y;
            Ans[ans++][2] = z;
            
            if(--a.amount) maxH.push(a);
            if(--b.amount) maxH.push(b);
            if(--c.amount) maxH.push(c);
        }
        cout << ans << endl;
        
        rep(i, ans) printf("%d %d %d\n", Ans[i][2], Ans[i][1], Ans[i][0]);
    }
    return 0;
}

发表于 2019-04-16 19:42:50 回复(0)