P8587题解

akakal · 2022-10-19 20:20:35 · 题解

这是本菜鸡的首篇题解，望通过^_^

思路

数据范围为 1\leq n\leq 10^6，1\leq h_i \leq 3\times 10^3。

数据很小啊，我们可以用桶排序来完成。

其实，让整个题难度变成黄题就是因为它的数据范围。一说到桶排序，整个题就简单起来了呢。

上次用桶排序的时候还是上次，太久远了

我们使用两个桶，先用一个桶记矿石高度，循环把所有合成的柱子高度放在另一个桶中就搞定了。

AC代码

#include <bits/stdc++.h>
using namespace std;
//数组大小 常量前用 k 符合规范
const int karr = 10010;
int b[karr],c[karr];
//max 为系统函数，所以用 _max
int n,sub,ans,ans2,_max;
int main(){
    //开启 cin cout 优化
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> sub;
        b[sub]++,_max = max(_max,sub);
    } 
    for(int i = 1; i <= _max; i++)
        for(int j = 1; j <= i; j++)
            if(b[i] && b[j]){
                if(i == j) c[i+j] += b[i] / 2;
                else c[i+j] += min(b[i],b[j]);
            }
    int _2max = _max * 2;
    for(int i = 1; i <= _2max; i++) ans = max(ans,c[i]);
    for(int i = 1; i <= _2max; i++) if(c[i] == ans) ans2++;
    cout << ans << " " << ans2 << endl;
    return 0;
}

第一次写题解，不知道怎么写，望大佬提醒！

审核大大辛苦了~