未了 NOI online2 T1题解

前言

考试时还以为能骗得点分呢。。。
传送门
根据题目，不难看出这是一道贪心题
我们把所有的魔法从高处往地处的使用，再求一个前缀和，就是使用到该魔法时西西弗斯需要用的年份，如果最高的魔法( 它的前缀和就是所有魔法都使用后西西弗斯需要花费的时间)使用了之后还是不能让西西弗斯大于$t_i$ti​年到达，就输出-1，反之，就在所有魔法中查找最小花费
注意：本题需要用到二分查找（其实就是个板子。。。）
特殊：如果西西弗斯按照没有阻拦的速度都无法在$t_i$ti​年内到达山顶，直接输出0

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
double b[200001],l,q,t,v,a[200001];
long long n;
int cmp(double x,double y){
	return x>y;
}
int main(){
	cin>>n>>l>>v;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n,cmp);//排序魔法的“能力”
	b[0]=l/v;//最好情况是不使用魔法
	for (int i=1;i<=n;i++){
		b[i]=double(a[i])/v+b[i-1];
	}
	scanf("%d",&q);
	while (q--){
		cin>>t;
		if (b[n]<=t){//如果用上所有魔法都不满足要求
			printf("-1\n");
			continue;
		}
		int l=0,r=n,ans=0;
		while (l<=r){
			int mid=(l+r)>>1;//相当于mid=(l+r)/2
			if (b[mid]>t){//如果大于了t，寻找花费更小的方案
				ans=mid;
				r=mid-1;
			}else{//如果还不能够让西西弗斯在大于t年时间走完
				l=mid+1;//往更长的时间找
			}
		} 
		printf("%d\n",ans);
	}
	return 0;
}