時間限制: 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)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。