昨晚cf的c求调
  • 板块学术版
  • 楼主dodo487
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/4/3 10:23
  • 上次更新2023/10/23 19:34:00
查看原帖
昨晚cf的c求调
544780
dodo487楼主2023/4/3 10:23
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
bool check(int k,int a,int b,int c){
	return (b-k)*(b-k)<4*a*c;
}
int n,m;
bool judge(int i){return 1<=i && i<=n;}
int a[N],b[N],c[N],k[N];
int twofind(int x){
	int l=1,r=n,ans=1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(k[mid]>=x) r=mid-1,ans=mid;
		else l=mid+1;
	}
	return ans;
}
signed main(){
	int T;
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=n+5;i++) k[i]=0;
		for(int i=1;i<=m+5;i++) a[i]=b[i]=c[i]=0;
		for(int i=1;i<=n;i++) scanf("%lld",&k[i]);
		for(int i=1;i<=m;i++){
			scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		}
		sort(k+1,k+1+n);
		n=unique(k+1,k+1+n)-k-1;
		for(int i=1;i<=m;i++){
			int x=twofind(b[i]);
			if(c[i]<=0){
				cout<<"NO"<<endl;
				continue;
			}
			if(judge(x)&&check(k[x],a[i],b[i],c[i])){
				cout<<"YES"<<endl<<k[x]<<endl;
			}else if(judge(x-1)&&check(k[x-1],a[i],b[i],c[i])){
				cout<<"YES"<<endl<<k[x-1]<<endl;
			}else if(judge(x+1)&&check(k[x+1],a[i],b[i],c[i])){
				cout<<"YES"<<endl<<k[x+1]<<endl;
			}else if(judge(x+2)&&check(k[x+2],a[i],b[i],c[i])){
				cout<<"YES"<<endl<<k[x+2]<<endl;
			}else if(judge(x-2)&&check(k[x-2],a[i],b[i],c[i])){
				cout<<"YES"<<endl<<k[x-2]<<endl;
			}else{
				cout<<"NO"<<endl;
			}
		}
		cout<<endl;
	}
}

由韦达定理可以知道(b-k)^2<4ac,所以就找到最接近b的k

2023/4/3 10:23
加载中...