OIer - FankerWang

一个不正经的信息学博客

CF1140C Playlist

《CF1140C Playlist》
原题链接

STL SET在竞赛中的使用
– SET支持高效的插入、删除和查询操作
– SET复杂度稳定,单个插入、删除和查询操作的复杂度均为O(log n)
– SET会自动实现容器维护,完成排序和去重操作

SET的基本语法
返回容器首个元素的位置指针:s.begin()
返回容器的最后一个元素的位置指针:s.end()
清空容器:s.clear()
判断是否为空(返回bool型):s.empty()
插入一个元素:s.insert()
删除一个元素:s.erase()
返回元素个数:s.size()

SET自定义比较器的使用
如果元素是结构体,可以直接把自定义比较器写在结构体内:

struct Info{
    string name;
    float score;
    //重载操作符<,自定义排序规则
    bool operator< (const Info &a)const{
        //return a.score < score;   //按score由大到小排列
        return a.score > score; //由小到大排列
    }
};
//定义SET时:
set<Info> s;

也可以自定义比较函数:

//自定义比较函数myComp,重载操作符 ()
struct myComp{
    bool operator() (const int &a, const int &b){
        return a > b;   //从大到小排序
        //return a < b; //从小到大排序
    }
};
//定义SET时:
set<int, myComp> s;

STL PAIR在竞赛中的使用
– pair用于合并两个数据,可用作需要返回两个数据的函数。
– 也可用于每个元素有两个特征值的情况

PAIR的基本语法
定义方法1:pair<int,int> p(创建一个新的pair对象p,它的两个元素都为int类型)
定义方法2:pair<int,int> p(1,2)(创建一个新的pair对象p,它的两个元素都为int类型,并分别初始化为1、2)
以v1和v2值创建一个新的pair对象:make_pair(v1,v2)(元素类型分别为v1和v2对应的类型)
访问方法:p.firstp.second
比较大小时先按first比较,如果相等再按second比较
比较是否相等需要first和second元素均相等
对pair进行排序时,可以使用sort函数
题目参考翻译

你有包含n首歌曲的歌单,对于第i首歌曲有两个数ti和bi分别表示这首歌曲的长度和分数。
从中选出最多不超过k首歌,使得所有选中歌曲的t值之和与所有选中歌曲中最小的b值的乘积最大。
请输出所有可能的组合中最大的乘积值。

解题思路
对于一个确定的bb_0,用贪心思路可以推理得:因为所有歌曲的长度都是正数,故需要从所有b值大于等于b_0的元素集合中找出k个数使得这k个元素的t值之和最大。
利用C++ STL,用pair来存储元素,用set来维护有序集合。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注