F. 连续非空子序列

Solution

很容易想到用前缀和并枚举端点解决该原题，即枚举 其中，,
找到满足 的即可。
实际上就是找到 前面满足 的 有多少个，设为 。
很容易想到二分这个 用主席树验证，时间复杂度 ，
由于 无法通过，那么考虑用离散化后对值域开树状数组，每次求和找前面有多少个，
时间复杂度是 。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48006491

J. 溪染的优惠券

Solution

很经典的01背包问题，但是需要转化，按 排序进行动态规划，证明如下：
设现在有两个物品属性分别为
假设当前 满足 ，此时的 可以以任意顺序取
最终结果均为
倘若 不满足 呢?此时结果的优劣与顺序有关，分别需要满足 或者
由于最终结果都是，显然我们是希望不等式的右边越小越好，所以我们希望构造
即 满足以上式子去动态规划是最优的。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48009663&returnHomeType=1&uid=105308122