[NOI Online-2 入门组]未了 题解
程序员文章站
2024-03-17 16:21:58
...
原题
题面传送门
不想打了,自己看吧。
题目解析
首先分析一下题目,不难发现,在高度为的地点使用魔法可以让Sisyphus多走年,我们可以利用贪心的思想,尽量使用上面的魔法,这样就可以使用更少。(C++的STL真好用一边sort就行了)
但是,我们一看数据范围:,如果用来除肯定会被卡精度,所以必须用来乘,记得开long long
为了方便查询,我们就可以加一个前缀和,用表示使用个魔法能让Sisyphus多走多少的路程。
因为对于任意的,都确保,满足单调性,所以可以进行二分查找,或者是进行排序然后离线递推了。
这里给出二分查找的代码,复杂度
代码
一定是某些人最爱的东西
#include<cstdio>
#include<algorithm>
#define maxn 200039
using namespace std;
typedef long long ll;
long long a[maxn],s[maxn];
int n,T,le,r,m;
ll l,v,t;
int cmp(ll x,ll y){
return x>y;
}
int main(){
freopen("endless.in","r",stdin);
freopen("endless.out","w",stdout);
int i,j;
scanf("%d%lld%lld",&n,&l,&v);
for(i=1;i<=n;i++)
scanf("%lld",&s[i]);
sort(s+1,s+n+1,cmp);
for(i=1;i<=n;i++)
a[i]=a[i-1]+s[i];
scanf("%d",&T);
while(T--){
scanf("%lld",&t);
t*=v;
if(t<l) printf("0\n");
else if(t>l+a[n]) printf("-1\n");
else{
le=0;r=n+1;
while(le+1<r){
m=(le+r)>>1;
if(t<l+a[m]) r=m;
else le=m;
}
if(r>n) printf("-1\n");
else printf("%d\n",r);
}
}
return 0;
}
如果抄代码记得关文件(