時間限制: 1 Sec 內(nèi)存限制: 512 MB
提交: 43 解決: 21
[提交][狀態(tài)][博客][加入收藏]
題目描述
visit_world 有一個商店，商店里賣NN個商品，第ii 個的價格為 a[i]a[i]
我們稱一個正整數(shù)KK 是美妙的，當(dāng)且僅當(dāng)我們可以在商店里選購若干個商品，使得價格之和落在區(qū)間 [K,2K][K,2K]中。
問：有多少個美妙的數(shù)。
輸入
第一行一個整數(shù)NN。
接下來一行 NN個整數(shù)，描述數(shù)組a[]a[]。

輸出
輸出一行一個整數(shù)，表示答案。
樣例輸入
3
1 2 3
樣例輸出
6
提示
解釋
可以證明1≤K≤61≤K≤6 都是美妙的，除此之外的數(shù)都不是美妙的。
樣例 2
/upload/file/20181017/20181017190720_44742.zip
數(shù)據(jù)范圍和子任務(wù)
子任務(wù) 1（30 分）：N≤100,ai≤100N≤100,ai≤100 .
子任務(wù) 2（20 分）：N≤100000,ai≤20N≤100000,ai≤20.
子任務(wù) 3（20 分）：N≤3,ai≤109N≤3,ai≤109 .
子任務(wù) 4（30 分）：N≤105,ai≤109N≤105,ai≤109 .

來源
hnsdfz國慶集訓(xùn)day2

題解
考慮子任務(wù)3，暴力求出每一種價值，設(shè)價值為W，那么它能貢獻(xiàn)的區(qū)間為[(W+1)/2,W]。然后區(qū)間求并即可。
考慮優(yōu)化求區(qū)間的次數(shù)，要避免全部枚舉，就假設(shè)已經(jīng)處理完前i-1個區(qū)間，考慮第a[i]對答案的貢獻(xiàn)。設(shè)前i-1個a[i]和為s，那么a[i]可能貢獻(xiàn)的區(qū)間為[(a[i]+1)/2,a[i]+s],又發(fā)現(xiàn)[(a[i]+s)/2,a[i]+s]這段區(qū)間一定能取到（所有物品都取即可）；那么在這些物品中去掉一些，必然能使和不小于s/2（因為個數(shù)大于一），故區(qū)間再向左移，依此類推，必能完全取到（a[i]+1）/2。 考慮與之前答案合并，若左端點小于之前的右端點，將右端點右移即可；若小于，則考慮想一種辦法使這個空缺的區(qū)間不對后面產(chǎn)生影響，即左端點小于后面所有區(qū)間的左端點，那么按a[i]從小到大排序即可。

總結(jié)

以上是生活随笔為你收集整理的3966: 购物(sum)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。