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

NOI Online #2 入门组第一题未了题解--zhengjun

程序员文章站 2024-03-17 16:13:10
...

这个题目名称十分诡异。

然后我可以提供两种做法,复杂度一样,都是O(nlogn)O(n\log n)的。

方法一

因为我们每一次使用魔法,就会让那个什么鬼畜的人物多走个aia_i天,所以就可以贪心,每一次只要取大的就可以了,然后因为每一次都要加在一起看看够不够,所以就可以二分了。

代码

#include<bits/stdc++.h>
#define maxn 200001
using namespace std;
int n,L,v,m,t;
long long a[maxn],sum[maxn];
bool cmp(const int &x,const int &y){
	return x>y;
}
int main(){
	scanf("%d%d%d",&n,&L,&v);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
	scanf("%d",&m);
	while(m--){
		scanf("%d",&t);
		int l=-1,r=n+1,mid;
		while(l+1<r){
			mid=(l+r)>>1;
			if(sum[mid]+L<=(long long)t*v)l=mid;
			else r=mid;
		}
		if(r>n)printf("-1\n");//我TM考试的时候没有换行全0分,样例的-1在最后面没有测出来qwq
		else printf("%d\n",r);
	}
	return 0;
}

方法二

因为每一次的查询的tt,如果t1<t2t_1<t_2t2t_2要选的魔法数量不会少于t1t_1的魔法数量,这样我们就可以先把tt拍个序,然后要注意记住原来的顺序然后就是模拟了。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,l,v;
int a[200001];
struct zj{
	int t,num,ans;
}t[200001];
bool cmp(const int &x,const int &y){
	return x>y;
}
bool cmp1(const zj &x,const zj &y){
	return x.t<y.t;
}
bool cmp2(const zj &x,const zj &y){
	return x.num<y.num;
}
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,cmp);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)scanf("%d",&t[i].t),t[i].num=i;
	sort(t+1,t+1+m,cmp1);
	int k=0;
	long long sum=l;
	for(int i=1;i<=m;i++){
		while(k<=n&&sum<=(long long)t[i].t*v)sum+=a[++k];
		if(sum<=(long long)t[i].t*v)t[i].ans=-1;
		else t[i].ans=k;
	}
	sort(t+1,t+1+m,cmp2);
	for(int i=1;i<=m;i++)printf("%d\n",t[i].ans);
	return 0;
}

谢谢–zhengjun