2866 未了 (前缀和 二分查找)
题目描述
由于触犯天神，Sisyphus 将要接受惩罚。
宙斯命 Sisyphus 推一块巨石上长度为L的山坡。Sisyphus匀速向上推的速度为每年v的长度（由于是匀速，故经过1/2年将能向上推v/2的长度）。然而，宙斯并不希望 Sisyphus太快到达山顶。宙斯可以施展n个魔法，若宙斯施展第i个魔法(1<=i<=n)，则当 Sisyphus 第一次到达位置ai时，他将会同巨石一起滚落下山底，并从头推起。（滚落的时间忽略不计，即可看作第一次到达位置ai后 Sisyphus 立即从山底重新出发）
Sisyphus的速度v=1，山坡的长度L=6，则他推石上山过程如下：
用3年走到位置3.
受ai=3的魔法影响，回到山底出发。
再用3年走到位置3，然后因为是第二次到达，ai=3的魔法不起作用。
用2年走到位置5。
受ai=5的魔法影响，回到山底出发。
用6年从山底走到山顶。花费的总时间为14年。
现在，宙斯有q个询问。对于第i个询问ti，宙斯想知道，他最少需要施展多少个魔法才能使 Sisyphus 到达山顶所用的年数大于ti。
输入
第一行三个整数n, L, v分别表示魔法的种类数，山坡的长度，Sisyphus 的速度。
第二行n个整数。第i个整数ai表示第i个魔法作用的位置。(1<=i<=n)
第三行一个整数q表示宙斯的询问个数。
接下来q行每行一个整数，第i行的整数ti表示宙斯的第i个询问。(1<=i<=q)
输出
输出q行，每行恰好一个整数，表示第i行的整数对应第i个询问的答案。
如果宙斯无论如何都不能使Sisyphus使用的年数大于ti，请输出-1。
样例输入
3 6 3
3 5 1
4
1
3
4
5
样例输出
0
1
2
-1
思路
问题可以简化为：对于每个询问t，求L至少加几个ai，使得(L+(ai...))/v>t
转变公式=>L+(ai...)>v*t => (ai...)>v*t-L
贪心思路：优先加大的ai （对ai排序）
对ai从大到小排序后，选前x个ai的和，使得这个和>=v*t-L
前x个ai的和，可以用前缀和预处理，sum[i]代表a[1]~a[i]的和 (sum[i]=sum[i-1]+a[i])
可以用二分查找大于等于v*t-L的最小sum[i]，找不到输出-1
注意：需要使用long long
using namespace std;typedef long long ll;int n,L,v,q,a[200005];ll sum[200005];int main(){scanf("%d%d%d",&n,&L,&v);for(int i=1; i<=n; i++) scanf("%d",&a[i]);sort(a+1,a+1+n);for(int i=1; i<=n; i++) sum[i]=sum[i-1]+a[n-i+1];scanf("%d",&q);while(q--){int t; scanf("%d",&t);ll w=(ll)t*v-L;int le=0, ri=n, ans=-1;while(le<=ri){int mid=(le+ri)/2;if(sum[mid]>w){ans=mid; ri=mid-1;}else le=mid+1;}printf("%d\n",ans);}return 0;}