本文主要是介绍3966: 购物(sum),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
时间限制: 1 Sec 内存限制: 512 MB
提交: 43 解决: 21
[提交][状态][博客][加入收藏]
题目描述
visit_world 有一个商店,商店里卖NN个商品,第ii 个的价格为 a[i]a[i]
我们称一个正整数KK 是美妙的,当且仅当我们可以在商店里选购若干个商品,使得价格之和落在区间 [K,2K][K,2K]中。
问:有多少个美妙的数。
输入
第一行一个整数NN。
接下来一行 NN个整数,描述数组a[]a[]。
输出
输出一行一个整数,表示答案。
样例输入
3
1 2 3
样例输出
6
提示
解释
可以证明1≤K≤61≤K≤6 都是美妙的,除此之外的数都不是美妙的。
样例 2
/upload/file/20181017/20181017190720_44742.zip
数据范围和子任务
子任务 1(30 分):N≤100,ai≤100N≤100,ai≤100 .
子任务 2(20 分):N≤100000,ai≤20N≤100000,ai≤20.
子任务 3(20 分):N≤3,ai≤109N≤3,ai≤109 .
子任务 4(30 分):N≤105,ai≤109N≤105,ai≤109 .
来源
hnsdfz国庆集训day2
题解
考虑子任务3,暴力求出每一种价值,设价值为W,那么它能贡献的区间为[(W+1)/2,W]。然后区间求并即可。
考虑优化求区间的次数,要避免全部枚举,就假设已经处理完前i-1个区间,考虑第a[i]对答案的贡献。设前i-1个a[i]和为s,那么a[i]可能贡献的区间为[(a[i]+1)/2,a[i]+s],又发现[(a[i]+s)/2,a[i]+s]这段区间一定能取到(所有物品都取即可);那么在这些物品中去掉一些,必然能使和不小于s/2(因为个数大于一),故区间再向左移,依此类推,必能完全取到(a[i]+1)/2。 考虑与之前答案合并,若左端点小于之前的右端点,将右端点右移即可;若小于,则考虑想一种办法使这个空缺的区间不对后面产生影响,即左端点小于后面所有区间的左端点,那么按a[i]从小到大排序即可。
这篇关于3966: 购物(sum)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!