三分法+例题（CF1355E - Restorer Distance）

在一个非单调函数中来确定其最值的方法

模板

整数的三分

int l = 1,r = 100; while(l < r) { int lmid = l + (r - l) / 3; int rmid = r - (r - l) / 3; lans = f(lmid),rans = f(rmid); // 求凹函数的极小值 if(lans <= rans) r = rmid - 1; else l = lmid + 1; // 求凸函数的极大值 if(lans >= rans) l = lmid + 1; else r = rmid - 1; } // 求凹函数的极小值 cout << min(lans,rans) << endl; // 求凸函数的极大值 cout << max(lans,rans) << endl;

浮点数的三分

const double EPS = 1e-9; while(r - l < EPS) { double lmid = l + (r - l) / 3; double rmid = r - (r - l) / 3; lans = f(lmid),rans = f(rmid); // 求凹函数的极小值 if(lans <= rans) r = rmid; else l = lmid; // 求凸函数的极大值 if(lans >= rans) l = lmid; else r = rmid; } // 输出 l 或 r 都可 cout << l << endl;

题目链接

https://codeforces.ml/problemset/problem/1355/E

题目大意：给你四个数N，A，R，M，其中N表示一共有N列墙，每列墙拥有的砖块数是h[i]，你需要通过增减砖块使每列墙的砖块数相同，可以进行三个操作：1、花费A，在某列墙上放一块砖，2、花费R，在某列墙中拿掉一块，3、花费M，将某一列墙中的一块放到令一列墙中。问你最少需要花费多少。

解题思路：首先写出一个count 函数，计算将墙都变为x块砖最少需要多少花费。利用三分法求这个函数在区间内的极小值。

代码：

#include<bits/stdc++.h> #define ll long long #define MOD 1000000007 #define INF 0x3f3f3f3f #define mem(a,x) memset(a,x,sizeof(a)) #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; ll h[100005]; ll N,A,R,M; ll count(ll x) { ll d=0,s=0; ll sum=0; for(int i=1;i<=N;i++){ if(h[i]>x){ d+=h[i]-x; }else{ s+=x-h[i]; } } if(M<A+R){ ll p=min(d,s); sum+=M*p; d-=p; s-=p; if(d!=0){ sum+=R*d; d=0; } if(s!=0){ sum+=A*s; } }else{ sum+=A*s; sum+=R*d; } return sum; } int main() { cin>>N>>A>>R>>M; ll maxn=0; for(int i=1;i<=N;i++){ scanf("%lld",&h[i]); maxn=max(h[i],maxn); } ll l=0,r=maxn; ll lans,rans; while(l<r) { ll lmid=l+(r-l)/3; ll rmid=r-(r-l)/3; lans=count(lmid),rans=count(rmid); //cout<<lmid<<" "<<rmid<<endl; if(lans>rans)l=lmid+1; else r=rmid-1; //cout<<l<<" "<<r<<endl; } cout<<min(lans,rans); return 0; }