欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[NOI Online-2 入门组]未了 题解

程序员文章站 2024-03-17 16:21:58
...

文章目录

原题

题面传送门
不想打LaTeX\LaTeX了,自己看吧。

题目解析

首先分析一下题目,不难发现,在高度为xx的地点使用魔法可以让Sisyphus多走2x2x年,我们可以利用贪心的思想,尽量使用上面的魔法,这样就可以使用更少。(C++的STL真好用一边sort就行了)
但是,我们一看数据范围:L,v109L,v\leq 10^9,如果用来除肯定会被卡精度,所以必须用来乘,记得开long long
为了方便查询,我们就可以加一个前缀和,用aia_i表示使用ii个魔法能让Sisyphus多走多少的路程。
因为对于任意的aia_i,都确保ai>ai1a_i>a_{i-1},满足单调性,所以可以进行二分查找,或者是进行排序然后离线O(n)O\left(n\right)递推了。
这里给出二分查找的代码,复杂度O(long2n+qlog2n)O\left(long_2n+qlog_2n\right)

代码

一定是某些人最爱的东西

#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;
}

如果抄代码记得关文件(

相关标签: 题解