【IOI2016】检测分子

题意:给定\(n\)个正整数\(w_{1…n}\),从中找出一些数的和在给定区间\([l,u]\)内。

保证\(u-l\ge w_{max}-w_{min}\)。

 

将原数列排序,那么答案一定是一段连续的区间。

假设存在一个解不是一段连续的区间,当我们选择中间一个元素时,一定可以丢掉两边的元素之一使得和仍然在区间内。

否则有\(sum+w_p-w_r<l\),\(sum+w_p-w_l>u\)

那么有\(u+w_l<l+w_r\),即\(u-l\le w_r-w_l\),不合题意

所以枚举右端点,直接一路扫过去即可。

当然同理也可以把中间的元素丢到两边,所以答案也可以是一个前缀+一个后缀

说点什么

您将是第一位评论人!

提醒
wpDiscuz