Day03 最佳拍照地点题解

「欢愉」花火

2026-08-14 20:48:04

发布于：浙江

3阅读

0回复

0点赞

原题链接：最佳拍照地点

关于y=ax²+bx+c与y=kx相切或相交
则必存在交点
即若两函数相交/相切
必定存在ax²+bx+c=kx
则∆>0;

∵ ∆=b²-4ac
即此处∆=(b-k)²-4ac
因为我们不想要存在交点
因此∆<0
∴(b-k)²-4ac<0

根据以上过程，可以得到一个自动检测是否符合要求的check函数

bool check(ll a,ll b,ll c,ll k){
    return (((b-k)*(b-k)-4*a*c)<0);
}

暴力思路：
由于我们已经知道对于特定的a[i]与b[j]是否符合条件
因此我们可以枚举a[i]与b[j]
代码实现：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool check(ll a,ll b,ll c,ll k){ //check函数，功能见上
    return (((b-k)*(b-k)-4*a*c)<0);
}
struct goose{
    ll a,b,c;
};
int main(){
	int _;
    cin>>_;
    while(_--){
        int n,m;
        scanf("%d %d",&m,&n);
        vector<goose> a(n+1);
        vector<ll> b(m+1);
        for(int i=1;i<=m;i++){
            cin>>b[i];
        }
        for(int i=1;i<=n;i++){
            cin>>a[i].a>>a[i].b>>a[i].c;
        }for(int i=1;i<=n;i++){ //枚举a[i]
            bool win=0;
            for(int j=1;j<=m;j++){ //枚举b[j]
                
                if(check(a[i].a,a[i].b,a[i].c,b[j])){  //如果符合条件，则输出YES
                    cout<<"YES\n";
                    cout<<b[j]<<endl;
                    win=1;
                    break;
                }
            }if(win==0) cout<<"NO\n";
        }cout<<endl;
        
    }
	return 0;
}

代码优化：
由于一个一个找符合条件的b[j]实在是太慢了，我们回顾公式

(b-k)²-4ac<0

我们要符合条件，则(b-k)²尽量小
可以观察到，k离b越接近，(b-k)²越小，更可能成功
对此，我们可以通过二分，寻找离b最近的k

对枚举b[j]的优化代码：

for(int i=1;i<=n;i++){
    ll k=a[i].b;
    ll fd=upper_bound(b.begin()+1,b.end(),k)-b.begin()-1;
    if(fd<m&&abs(b[fd]-k)>abs(b[fd+1]-k)){
        fd++;
    }
    if(check(a[i].a,a[i].b,a[i].c,b[fd])){
        cout<<"YES\n";
        cout<<b[fd]<<endl;
    } else cout<<"NO\n";
}cout<<endl;

最终得到AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool check(ll a,ll b,ll c,ll k){
    return (((b-k)*(b-k)-4*a*c)<0);
}
struct goose{
    ll a,b,c;
};
int main(){
	int _;
    cin>>_;
    while(_--){
        int n,m;
        scanf("%d %d",&m,&n);
        vector<goose> a(n+1);
        vector<ll> b(m+1);
        for(int i=1;i<=m;i++){
            cin>>b[i];
        }
        sort(b.begin()+1,b.end());
        for(int i=1;i<=n;i++){
            cin>>a[i].a>>a[i].b>>a[i].c;
        }
        b[0]=-1e18;
        for(int i=1;i<=n;i++){
            ll k=a[i].b;
            ll fd=upper_bound(b.begin()+1,b.end(),k)-b.begin()-1;
            if(fd<m&&abs(b[fd]-k)>abs(b[fd+1]-k)){
                fd++;
            }
            if(check(a[i].a,a[i].b,a[i].c,b[fd])){
            	cout<<"YES\n";
            	cout<<b[fd]<<endl;
			} else cout<<"NO\n";
        }cout<<endl;
        
    }
	return 0;
}
for(int i=1;i<=n;i++){
    ll k=a[i].b;
    ll fd=upper_bound(b.begin()+1,b.end(),k)-b.begin()-1;
    if(fd<m&&abs(b[fd]-k)>abs(b[fd+1]-k)){
        fd++;
    }
    if(check(a[i].a,a[i].b,a[i].c,b[fd])){
        cout<<"YES\n";
        cout<<b[fd]<<endl;
    } else cout<<"NO\n";
}cout<<endl;

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论