洛谷刷题7.25

P1102 A-B 数对 - 洛谷

 该题可用尺取法，二分法。也可用map比较省事，nlogn的复杂度可以接受

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll>q; 
ll n,c,arr[200005],ans=0;
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++){
	cin>>arr[i];
	q[arr[i]]++;
}
for(int i=1;i<=n;i++){
	if(q.find(arr[i]+c)!=q.end()) ans+=q[arr[i]+c];
}
cout<<ans;
    return 0;
}

P1462 通往奥格瑞玛的道路 - 洛谷

 二分+dijsktra求最短路

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct bian{
	ll u,l;
	bool operator<(const bian &s1)const
	{
		return s1.l<l;
	}
};
ll n,m,k,f[10005],a,b,c,s[10005],d[10005];
bool vis[10005];
vector<bian>arr[10005];
bool check(ll x){
	memset(d,0x3f,sizeof(d));
	memset(vis,false,sizeof(vis));
	d[1]=0;
	priority_queue<bian>r; 
	if(f[1]<=x) r.push(bian{1,0});
	while(!r.empty()){
		a=r.top().u;
		if(!vis[a]){
			vis[a]=true;
			for(auto it:arr[a]){
				if(f[it.u]<=x){
					if(d[it.u]>d[a]+it.l){
						d[it.u]=d[a]+it.l;
						r.push(bian{it.u,d[it.u]});	
					}
				}
			}
		}
		r.pop();
	}
	if(d[n]<=k) return true;
	else return false;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
	cin>>f[i];
	s[i]=f[i];
}
sort(s+1,s+1+n);
for(int i=0;i<m;i++){
	cin>>a>>b>>c;
	arr[a].push_back(bian{b,c});
	arr[b].push_back(bian{a,c});
}
int l=0,r=n+1;
while(l+1<r){
	int mid=(l+r)/2;
	if(check(s[mid])) r=mid;
	else l=mid;
}
if(r==n+1) cout<<"AFK";
else cout<<s[r];
    return 0;
}

 P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G - 洛谷

 依旧二分答案

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,arr[100005],sum;
bool check(ll x){
	ll now=arr[1];
	sum=1;
	for(int i=2;i<=n;i++){
		if(arr[i]-now>=x){
			sum++;
			now=arr[i];
		}
		if(sum>=m) return true;
	}
	return false;
} 
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
	cin>>arr[i];
}
sort(arr+1,arr+1+n);
ll l=0,r=1e9;
while(l+1<r){
	ll mid=(l+r)/2;
	if(check(mid)) l=mid;
	else r=mid;
}
cout<<l;
    return 0;
}

P1419 寻找段落 - 洛谷

 二分答案+优先队列优化动态规划

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,s,t,a[100005];
double b[100005],sum[100005];
deque<int>q;
void put(int x){
	while(!q.empty()&&sum[q.back()]>=sum[x]){
		q.pop_back();
	}
	q.push_back(x);
}
void out(int x){
	while(!q.empty()&&q.front()<x){
		q.pop_front();
	}
}
bool check(double x){
	sum[0]=0;
	for(int i=1;i<=n;i++){
		b[i]=a[i]-x;
		sum[i]=sum[i-1]+b[i];
	}	
	q.clear();
	int now=0;
	for(int i=1;i<=n;i++){
		while(now<=i-s){
			put(now++);
		}
		out(i-t);
		if(!q.empty()){
			if(sum[i]-sum[q.front()]>=0) return true; 
		}
	}
	return false;
} 
int main(){
cin>>n>>s>>t;
for(int i=1;i<=n;i++)
	cin>>a[i];
double l=-1e4-1,r=1e4+1;
while(l+0.0001<r){
	double mid=(l+r)/2;
	if(check(mid)) l=mid;
	else r=mid;
}
cout<<fixed<<setprecision(3)<<l;
    return 0;
}

P3382 三分 - 洛谷

 可用求导+二分解决

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
double l,r,a[15];
double f(double x){
	double ans=0,temp=1;
	for(int i=n+1;i>=1;i--){
		ans+=a[i]*temp;
		temp*=x;
	}
	return ans;
}
double dao(double x){
	return 1000000*(f(x+0.000001)-f(x));
}
int main(){
cin>>n>>l>>r;
for(int i=1;i<=n+1;i++){
	cin>>a[i];
}
while(l+0.000001<r){
	double mid=(l+r)/2;
	if(dao(mid)>0) l=mid;
	else r=mid;
}
cout<<fixed<<setprecision(5)<<l;
    return 0;
}

P1883 【模板】三分 | 函数 - 洛谷

 直接模板

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n, t;
double a[10005], b[10005], c[10005];

double f(double x) {
    double ans = a[1] * x * x + b[1] * x + c[1];
    for (int i = 2; i <= n; i++) {
        double val = a[i] * x * x + b[i] * x + c[i];
        if (val > ans) 
            ans = val;
    }
    return ans;
}

void work() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    double l = 0.0, r = 1000.0;
    while (r - l > 1e-10) {
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (f(m1) > f(m2)) 
            l = m1;
        else 
            r = m2;
    }
    double ans = f((l + r) / 2);
    if (fabs(ans) < 1e-8) ans = 0.0; // 避免输出-0.0000
    printf("%.4f\n", ans);
}

int main() {
    cin >> t;
    while (t--) {
        work();
    }
    return 0;
}