雅礼NOIP2018集训 day5 赛
题面
由于出题人思维枯竭所以想不出好玩的背景。 有 n 个物品,第 i 个物品的价格是 vi,有两个人,每个人都喜欢 n 个物品中的一些物 品。 要求选出正好 m 个物品,满足选出的物品中至少有 k 个物品被第一个人喜欢,k 个物 品被第二个人喜欢。并求出最小的价格和。
大概思路
把物品分为4类 A类:两个人都喜欢的物品 B类:只有第一个人喜欢的物品 C类:只有第二个人喜欢的物品 D类:所有物品
先把四个数组先从小到大排序
我们先全部选A类 然后从大到小枚举A类选的个数 每少选一个A类就分别B、C类从小到大选一个数 把选过的数在D类标记然后用二分查询 D类需要用树状数组或线段数维护
标签:day5,NOIP2018,雅礼,喜欢,物品,集训 From: https://www.cnblogs.com/blln/p/16613935.html