2019年海淀区青少年程序设计挑战活动复赛小学组C++试题第6题题解

C++ 少儿编程 395浏览 0评论
2019年海淀区青少年程序设计题解

6

盒子

    分析:对盒子的强度值进行排序有利于进行分组。我们先按盒子强度从小到大进行排序。可总结出以下的性质:

    1、如果一个盒子的强度是x,那么它上面的盒子的个数就是<=x。

    2、如果一个盒子的强度大于上面盒子的个数,那么这个盒子就是需要重新另开一组。

    为了方面处理堆的数量变化以及堆的个数,我们可以利用stl中的集合,因为数值中有重复的值,我们选用multiset。这个集合当中的每个元素代表每个堆有多少个盒子。我们从小到大遍历盒子的强度值数组,只有堆的个数小于等于x,x才能加入该堆的最底部。如果最小堆的个数大于x,那么就要为x新建一堆。最后我们输出集合的个数即可。代码如下:

#include <iostream>

#include <set>

#include <algorithm>

using namespace std;

int x[500005];

int main(){

    int n;

    cin >> n;

    for(int i =1;i <= n;i++){

        cin >> x[i];

    }

    sort(x,x+n);//排序 0 1 1 2 2

    //myse每个元素代表每个堆有几个盒子

    multiset<int,greater<int>> myset;

    for(int i =1;i <= n;i++){

        //对于降序集合,lower_bound得到的是第一个小于x[i]的元素的位置

        multiset<int>::iterator it = myset.lower_bound(x[i]);

        //如果最小堆的个数大于x[i],说明要为x[i]新建一个堆

        if(it == myset.end()){

            myset.insert(1);

        }

        else{

            //当堆的个数小于等于x[i]x[i]才能加入该堆的最底部。

            //把元素加到这个堆里时,堆的元素个数加1

            int cnt =*it +1;

            myset.erase(it);

            myset.insert(cnt);

        }

    }

    cout << myset.size()<< endl;

    return 0;

}

转自公众号:
noip案例讲解

您必须 登录 才能发表评论!