首页 > [NOIP2011]聪明的质监员
开通博客写题解
头像 19_hanhan
发表于 2020-06-07 23:57:09
题目 题目描述： 小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到 n 逐一编号，每个矿石都有自己的重量wi以及价值vi。 检验矿产的流程是： 1、给定m个区间[Li，Ri]； 2、选出一个参数W； 3、对于一个区间[Li，Ri] 展开全文
去ta的博客 赞 (9) 回复(3) 收起
头像 pphkaa
发表于 2020-04-11 23:03:35
首先我们来看看观察每个区间的值就以题目中的示例为例子解释一下 对应区间段1-5由于可加的物品的重量必须大于等于W（4）故在1-5中只有4，5两个可加贡献为 25+25=20；2是因为有两个数符号条件 在2-4中，只有4一个可加贡献为1*5=5； 3-3中，没有可以加的贡献0故这样当w取4时 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-09-06 16:32:58
从题中描述可以看出w和检验结果之间有一定关系：w越大检验结果越小，w越小检验结果越大。从而得到w的结果具有一个单调的性质。然后根据这个性质可以考虑二分w的做法。 在二分的过程中，如果Y>S那么w就得增大，如果Y<S那么w就得减小，如果Y==S那么直接退出就可以了。但我们最终的答案是 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 已注销
发表于 2020-06-28 10:48:57
思路分析:观察式子可以发现要满足 最小，即 与 越接近越好。在观察检验值的公式可以发现若 越大，满足 和 将减小，导致检验值的减小。所以我们可以发现当 时我们要增大 ，当 时减小 ,这才能使 与 不断接近。其中检验值的计算可以通过前缀和优化。 代表前 个中满足条件的元素个数, 同理。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-06-07 18:09:25
二分+前缀和 求解最小值，观察题目给出的判断条件，W随着变大时，区间中符合要求的会减少，同时所有，所以也随着变小，求得Y也是递减，可以得知W和Y是满足二分的关系。在求解每一个时，运用到前缀和的思想O(1)实现。 总的时间复杂度 Code #pragma GCC target("avx,sse2,s 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 savage
发表于 2019-09-06 16:38:11
算法知识点：二分，前缀和 复杂度： 解题思路： 观察每个区间的值且 且。 当 增大时，区间 中满足要求的会减少，同时所有 ，因此 的值也会减少。 由于 ，所以 随 单调递减。 因此我们可以二分出距离 最近的值。 剩下的问题是当 确定之后，我们 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 三大爷的剑
发表于 2021-10-13 18:04:23
技巧     二分    前缀和 思路     Yi表达式意思  ： 统计区间内满足重量大于假设值的数量  *  满足条件的矿石总和     由于Yi 特性（范围操作 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 imagination666
发表于 2022-03-10 12:18:24
题目解析 看公式就看了半天，总结来说就是，自己设定一个W，用区域内比这个W重的物品数量*这些物品的价值之和=检验值。 求检验值与标准值之间最小的差值。 通过简单的分析可以得出，当我们选定的W约小的时候，所求的Y越大，相反当W越大的时候，Y就越小，所以有单调性，适用于二分查找。 于是有以下代码： im 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 savage
发表于 2019-08-31 16:29:23
题目描述 小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到 n 逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是： 1、给定m个区间[Li，Ri]； 2、选出一个参数W； 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”