問題引入

首先我們來看一下這樣一個問題

[NOIP2001 提高組] 一元三次方程求解

題目描述

有形如：$a{x}^3+b{x}^2+cx+d=0$ 這樣的一個一元三次方程。給出該方程中各項的系數(shù)（$a,b,c,d$ 均為實數(shù)），并約定該方程存在三個不同實根（根的范圍在 $?100$ 至 $100$ 之間），且根與根之差的絕對值 $\ge 1$。要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后 $2$ 位。

提示：記方程 $f(x)=0$，若存在 $2$ 個數(shù) $x_1$ 和 $x_2$，且 $x_1<x_2$，$f(x_1)\times f(x_2)<0$，則在 $(x_1,x_2)$ 之間一定有一個根。

輸入格式

一行，$4$ 個實數(shù) $a,b,c,d$。

輸出格式

一行，$3$ 個實根，從小到大輸出，并精確到小數(shù)點后 $2$ 位。

樣例 #1

樣例輸入 #1

1 -5 -4 20

樣例輸出 #1

-2.00 2.00 5.00

提示

【題目來源】

NOIP 2001 提高組第一題

思路分析

這道題的數(shù)據(jù)范圍相當之小，用暴力就能過

AC代碼

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
double a,b,c,d;
inline void check(double i){double j=i+0.001;double y1=a*i*i*i+b*i*i+c*i+d;double y2=a*j*j*j+b*j*j+c*j+d;if(y1>=0&&y2<=0||y1<=0&&y2>=0)printf("%.2lf ",(i+j)/2);
}
int  main() {scanf("%lf%lf%lf%lf",&a,&b,&c,&d);for(double i=-100;i<=100;i+=0.001)check(i);return 0;
}

思考

如果這道題的解空間再開打一下，開到1000,10000，那么暴力就一定過不去了

這時候就需要我們的二分法閃亮登場了

關于二分和三分

二分在下之前寫過一篇博客講解

戳這里

二分解決的問題都有一個共同的性質(zhì)：單調(diào)性

而如果某個問題的解空間是單峰的，不管是向外凸還是向內(nèi)凹，都可以用另一種算法解決，三分

顧名思義，三分就是一種把解空間分成三段的算法，答案一定在某個段內(nèi)，時間是$lo{g}_3(n)$但也是$O(log(n))$的算法

簡單來說，二分解決零點問題，三分解決極值問題

例題講解

進擊的奶牛

題目描述

Farmer John 建造了一個有 $N$（$2\le N\le 10^5$) 個隔間的牛棚，這些隔間分布在一條直線上，坐標是 $x_1,x_2,?,x_N$（$0\le x_i\le 10^9$）。

他的 $C$（$2\le C\le N$）頭牛不滿于隔間的位置分布，它們?yōu)榕Ｅ锢锲渌呐５拇嬖诙鴳嵟榱朔乐古Ｖg的互相打斗，Farmer John 想把這些牛安置在指定的隔間，所有牛中相鄰兩頭的最近距離越大越好。那么，這個最大的最近距離是多少呢？

輸入格式

第 $1$ 行：兩個用空格隔開的數(shù)字 $N$ 和 $C$。

第 $2～N+1$ 行：每行一個整數(shù)，表示每個隔間的坐標。

輸出格式

輸出只有一行，即相鄰兩頭牛最大的最近距離。

樣例 #1

樣例輸入 #1

5 3
1
2
8
4
9

樣例輸出 #1

3

思路

二分每一種可能的間隔長度，檢查是否符合條件

AC代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100005;
int n,m,x[N];
template<typename T>
inline void read(T &x)
{x=0;char c = getchar();int s = 1;while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}x*=s;
}
template<typename T>
inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;
}
inline bool check(int d){int cow=1;int rgt=x[1]+d;for(int i=2;i<=n;i++){if(x[i]<rgt)continue;++cow;rgt=x[i]+d;}return cow>=m;
}
int main(){read(n),read(m);for(int i=1;i<=n;i++)read(x[i]);sort(x+1,x+n+1);int l=0,r=x[n]-x[1];while(l<=r){int mid=(l+r)>>1;if(check(mid))l=mid+1;else r=mid-1;} write(r);printf("\n");return 0;
}

平均數(shù)

題目描述

給一個長度為 $n$ 的數(shù)列，我們需要找出該數(shù)列的一個子串，使得子串平均數(shù)最大化，并且子串長度 $\ge m$。

輸入格式

第一行兩個整數(shù) $n$ 和 $m$。

接下來 $n$ 行，每行一個整數(shù) $a_i$，表示序列第 $i$ 個數(shù)字。

輸出格式

一個整數(shù)，表示最大平均數(shù)的 $1000$ 倍，如果末尾有小數(shù)，直接舍去，不要用四舍五入求整。

樣例 #1

樣例輸入 #1

10 6
6
4
2
10
3
8
5
9
4
1

樣例輸出 #1

6500

提示

數(shù)據(jù)規(guī)模與約定

• 對于 $60\%$ 的數(shù)據(jù)，保證 $m\le n\le 10^4$；
• 對于 $100\%$ 的數(shù)據(jù)，保證 $1\le m\le n\le 10^5$，$0\le a_i\le 2000$。

AC代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const double eps=1e-10;
template<typename T>
inline void read(T &x)
{x=0;char c = getchar();int s = 1;while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}x*=s;
}
template<typename T>
inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;
}
int n,len,a[100010];
double b[100010],sum[100010];
int main(){read(n),read(len);for(int i=1;i<=n;i++)read(a[i]);double l=-1e6,r=1e6,mid;while(r-l>eps){mid=(l+r)/2;for(int i=1;i<=n;i++){b[i]=a[i]-mid;sum[i]=sum[i-1]+b[i];}double minn=1e9,tmp=-1e9;for(int i=len;i<=n;i++){minn=min(minn,sum[i-len]);tmp=max(tmp,sum[i]-minn);}if(tmp>-eps)l=mid;else r=mid;}cout<<(int)((r+eps)*1000)<<endl;return 0;
}

Dropping Test

題目描述

在某個課程中，你需要進行 $n$ 次測試。

如果你在共計 $b_i$ 道題的測試 $i$ 上的答對題目數(shù)量為 $a_i$，你的累積平均成績就被定義為

$$100\times \frac{\sum _{i=1}^n{a}_i}{\sum _{i=1}^n{b}_i}$$

給定您的考試成績和一個正整數(shù) $k$，如果您被允許放棄任何 $k$ 門考試成績，您的累積平均成績的可能最大值是多少。

假設您進行了 $3$ 次測試，成績分別為 $5/5,0/1$ 和 $2/6$。

在不放棄任何測試成績的情況下，您的累積平均成績是

$$100\times \frac{5+0+2}{5+1+6}=50$$

然而，如果你放棄第三門成績，則您的累積平均成績就變成了

$$100\times \frac{5+0}{5+1}\approx 83.33\approx 83$$

輸入格式

輸入包含多組測試用例，每個測試用例包含三行。

對于每組測試用例，第一行包含兩個整數(shù) $n$ 和 $k$。

第二行包含 $n$ 個整數(shù)，表示所有的 $a_i$。

第三行包含 $n$ 個整數(shù)，表示所有的 $b_i$。

當輸入用例 $n=k=0$ 時，表示輸入終止，且該用例無需處理。

輸出格式

對于每個測試用例，輸出一行結(jié)果，表示在放棄 $k$ 門成績的情況下，可能的累積平均成績最大值。

結(jié)果應四舍五入到最接近的整數(shù)。

樣例 #1

樣例輸入 #1

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

樣例輸出 #1

83
100

提示

數(shù)據(jù)范圍 $1\le n\le 1000$, $0\le k<n$, $0\le a_i\le b_i\le 10^9$。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
const double eps=1e-8;
int n,k;
double a[1010],b[1010],tmp[1010];
inline bool check(double m){double cnt=0;for(int i=1;i<=n;i++){tmp[i]=a[i]-b[i]*m;}sort(tmp+1,tmp+1+n);for(int i=n;i>k;i--){cnt+=tmp[i];}return cnt>=0;
}
int main(){while(scanf("%d%d",&n,&k)){if(n==0&&k==0)break;for(int i=1;i<=n;i++)scanf("%lf",&a[i]);for(int i=1;i<=n;i++)scanf("%lf",&b[i]);double st=0,ed=100;while(fabs(ed-st)>=eps){double mid=st+(ed-st)/2;if(check(mid))st=mid;else ed=mid;}st*=100.0;printf("%.0lf\n",st);}return 0;
}

【模板】三分 | 函數(shù)

題目描述

給定 $n$ 個二次函數(shù) $f_1(x),f_2(x),\dots ,f_n(x)$（均形如 $a{x}^2+bx+c$），設 F ( x ) = max ? { f 1 ( x ) , f 2 ( x ) , . . . , f n ( x ) } F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\} F(x)=max{f1?(x),f2?(x),...,fn?(x)}，求 $F(x)$ 在區(qū)間 $[0,1000]$ 上的最小值。

輸入格式

輸入第一行為正整數(shù) $T$，表示有 $T$ 組數(shù)據(jù)。

每組數(shù)據(jù)第一行一個正整數(shù) $n$，接著 $n$ 行，每行 $3$ 個整數(shù) $a,b,c$，用來表示每個二次函數(shù)的 $3$ 個系數(shù)，注意二次函數(shù)有可能退化成一次。

輸出格式

每組數(shù)據(jù)輸出一行，表示 $F(x)$ 的在區(qū)間 $[0,1000]$ 上的最小值。答案精確到小數(shù)點后四位，四舍五入。

樣例 #1

樣例輸入 #1

2
1
2 0 0
2
2 0 0
2 -4 2

樣例輸出 #1

0.0000
0.5000

提示

對于 $50\%$ 的數(shù)據(jù)，$n\le 100$。

對于 $100\%$ 的數(shù)據(jù)，$T<10$，$n\le 10^4$，$0\le a\le 100$，$|b|\le 5\times 10^3$，$|c|\le 5\times 10^3$。

AC代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define eps 1e-10
using namespace std;
int n,t;
struct f{int a,b,c;
}s[10005];
template<typename T>
inline void read(T &x)
{x=0;char c = getchar();int s = 1;while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}x*=s;
}
template<typename T>
inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;
}
inline double calc(double num){double maxn=-1e9;for(int i=1;i<=n;i++){maxn=max(maxn,s[i].a*num*num+s[i].b*num+s[i].c);}return maxn;
}
int main(){read(t);while(t--){read(n);for(int i=1;i<=n;i++){read(s[i].a);read(s[i].b);read(s[i].c);}double l=0,r=1000,midl,midr;while(r-l>eps){midl=l+(r-l)/3,midr=r-(r-l)/3;if(calc(midl)>calc(midr))l=midl;else r=midr;}printf("%.4lf\n",calc(l));}return 0;
}

Doremy’s IQ

題面翻譯

題目描述

哆來咪·蘇伊特參加了 $n$ 場比賽。 比賽 $i$ 只能在第 $i$ 天進行。比賽 $i$ 的難度為 $a_i$。最初，哆來咪的 IQ 為 $q$ 。 在第 $i$ 天，哆來咪將選擇是否參加比賽 i。只有當她當前的 IQ 大于 $0$ 時，她才能參加比賽。

如果哆來咪選擇在第 $i$ 天參加比賽 $i$，則會發(fā)生以下情況：

• 如果 $a_i>q$，哆來咪會覺得自己不夠聰明，所以 $q$ 將會減 $1$；
• 否則，什么都不會改變。

如果她選擇不參加比賽，一切都不會改變。哆來咪想?yún)⒓颖M可能多的比賽。請給哆來咪一個解決方案。

輸入格式

第一行包含一個正整數(shù) $t$ ($1\le t\le 10^4$) ，表示測試數(shù)據(jù)的組數(shù)。

第二行包含兩個整數(shù) $n$ 和 $q$ ($1\le n\le 10^5$, $1\le q\le 10^9$)，表示比賽次數(shù)和哆來咪最開始時的 IQ。

第三行包含 $n$ 個整數(shù) $a_1,a_2?a_n$($1\le a_i\le 10^9$)，表示每場比賽的難度。

數(shù)據(jù)保證 $n$ 之和不超過 $10^5$。

輸出格式

對于每組數(shù)據(jù)，輸出一個二進制字符串 $s$，如果哆來咪應該選擇參加比賽 $i$，則 $s_i=1$，否則 $s_i=0$。 字符串中 $1$ 的數(shù)量應該盡可能的多，并且當她的 IQ 為 $0$ 或更低時，她不應該參加比賽。

如果有多個解決方案，你可以輸出任意一個。

樣例說明

在第一個測試用例中，哆來咪參加了唯一的比賽。她的 IQ 沒有下降。

在第二個測試用例中，哆來咪參加了兩個比賽。在參加比賽 $2$ 后，她的 IQ 下降了 $1$。

在第三個測試用例中，哆來咪參加了比賽 $1$ 和比賽 $2$。她的 IQ 在參加比賽 $2$ 后降至 $0$，因此她無法參加比賽 $3$。

題目描述

Doremy is asked to test $ n $ contests. Contest $ i $ can only be tested on day $ i $ . The difficulty of contest $ i $ is $ a_i $ . Initially, Doremy’s IQ is $ q $ . On day $ i $ Doremy will choose whether to test contest $ i $ or not. She can only test a contest if her current IQ is strictly greater than $ 0 $ .

If Doremy chooses to test contest $ i $ on day $ i $ , the following happens:

• if $ a_i>q $ , Doremy will feel she is not wise enough, so $ q $ decreases by $ 1 $ ;
• otherwise, nothing changes.

If she chooses not to test a contest, nothing changes.Doremy wants to test as many contests as possible. Please give Doremy a solution.

輸入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The description of the test cases follows.

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n \le 10^5 $ , $ 1 \le q \le 10^9 $ ) — the number of contests and Doremy’s IQ in the beginning.

The second line contains $ n $ integers $ a_1,a_2,\cdots,a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the difficulty of each contest.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

輸出格式

For each test case, you need to output a binary string $ s $ , where $ s_i=1 $ if Doremy should choose to test contest $ i $ , and $ s_i=0 $ otherwise. The number of ones in the string should be maximum possible, and she should never test a contest when her IQ is zero or less.

If there are multiple solutions, you may output any.

樣例 #1

樣例輸入 #1

5
1 1
1
2 1
1 2
3 1
1 2 1
4 2
1 4 3 1
5 2
5 1 2 4 3

樣例輸出 #1

1
11
110
1110
01111

提示

In the first test case, Doremy tests the only contest. Her IQ doesn’t decrease.

In the second test case, Doremy tests both contests. Her IQ decreases by $ 1 $ after testing contest $ 2 $ .

In the third test case, Doremy tests contest $ 1 $ and $ 2 $ . Her IQ decreases to $ 0 $ after testing contest $ 2 $ , so she can’t test contest $ 3 $ .

AC代碼

#include<cstdio>
#include<cstring>
using namespace std;
#define N 100000
int t,n,q,a[N+2],pos;
bool ans[N+2];
inline bool check(int x){int w=q;for(int i=x+1;i<=n;++i){if(a[i]>w)--w;}return w>=0;
}
int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&q);for(int i=1;i<=n;++i)scanf("%d",a+i);for(int l=0,r=n,mid;l<=r;){mid=(l+r)>>1;if(check(mid)){pos=mid;r=mid-1;}else l=mid+1;}for(int i=1;i<=pos;++i){if(a[i]<=q)ans[i]=true;else ans[i]=false;}for(int i=pos+1;i<=n;++i)ans[i]=true;for(int i=1;i<=n;++i)printf("%d",ans[i]);printf("\n");}return 0;
}

Empty Graph

題面翻譯

給定一個長為 $n$ 的序列 $a$。

定義一個 $n$ 個點的無向完全圖，點 $l$ 和點 $r$ 之間的距離為 min ? i ∈ [ l , r ] { a i } \min\limits_{i\in[l,r]}\{a_i\} i∈[l,r]min?{ai?}。

你可以進行 $k$ 次操作，每次操作可以選定 $?i\in [1,n]$ 并將 $a_i$ 賦值為一個 $[1,10^9]$ 的整數(shù)。請最大化這個圖的直徑。

設 $d(u,v)$ 表示 $u$ 到 $v$ 的最短路徑長度，圖的直徑定義為 $\underset{1\le u<v\le n}{\max }d(u,v)$。

輸出最大化的直徑長度。

題目描述

— Do you have a wish?

— I want people to stop gifting each other arrays.

O_o and Another Young Boy

An array of $ n $ positive integers $ a_1,a_2,\ldots,a_n $ fell down on you from the skies, along with a positive integer $ k \le n $ .

You can apply the following operation at most $ k $ times:

• Choose an index $ 1 \le i \le n $ and an integer $ 1 \le x \le 10^9 $ . Then do $ a_i := x $ (assign $ x $ to $ a_i $ ).

Then build a complete undirected weighted graph with $ n $ vertices numbered with integers from $ 1 $ to $ n $ , where edge $ (l, r) $ ( $ 1 \le l < r \le n $ ) has weight $ \min(a_{l},a_{l+1},\ldots,a_{r}) $ .

You have to find the maximum possible diameter of the resulting graph after performing at most $ k $ operations.

The diameter of a graph is equal to $ \max\limits_{1 \le u < v \le n}{\operatornamevxwlu0yf4(u, v)} $ , where $ \operatornamevxwlu0yf4(u, v) $ is the length of the shortest path between vertex $ u $ and vertex $ v $ .

輸入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). Description of the test cases follows.

The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \le n \le 10^5 $ , $ 1 \le k \le n $ ).

The second line of each test case contains $ n $ positive integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le 10^9 $ ).

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

輸出格式

For each test case print one integer — the maximum possible diameter of the graph after performing at most $ k $ operations.

樣例 #1

樣例輸入 #1

6
3 1
2 4 1
3 2
1 9 84
3 1
10 2 6
3 2
179 17 1000000000
2 1
5 9
2 2
4 2

樣例輸出 #1

4
168
10
1000000000
9
1000000000

提示

In the first test case, one of the optimal arrays is $ [2,4,5] $ .

The graph built on this array:

$ \operatornamevxwlu0yf4(1, 2) = \operatornamevxwlu0yf4(1, 3) = 2 $ and $ \operatornamevxwlu0yf4(2, 3) = 4 $ , so the diameter is equal to $ \max(2,2,4) = 4 $ .

AC代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=100010;
typedef long long ll ;
ll t,n,k,a[N],pre[N],sub[N];
template<typename T>
inline void read(T &x)
{x=0;char c = getchar();ll s = 1;while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}x*=s;
}
template<typename T>
inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;
}
inline bool check(ll pos){for(ll i=1;i<=n;i++)pre[i]=pre[i-1]+(ll)((a[i]<<1)<pos);for(ll i=n;i;i--)sub[i]=sub[i+1]+(ll)((a[i]<<1)<pos);ll minx=0x3f3f3f3f;for(ll i=1;i<n;i++)minx=min(minx,pre[i-1]+sub[i+2]+(ll)(a[i] < pos) + (ll)(a[i + 1] < pos));return minx<=k;
}
int main(){read(t);while (t--) {read(n),read(k);memset(pre, 0, sizeof(pre));memset(sub, 0, sizeof(sub));for (ll i = 1; i <= n; i++) read(a[i]);ll l = 0, r = 1e9, ans = 0;while (l <= r) {ll mid = l + r >> 1;if (check(mid)) {l=mid+1;ans=mid;} else r = mid-1;}write(ans);printf("\n");}return 0;
}

這是我的第十二篇文章，如有紕漏也請各位大佬指正

辛苦創(chuàng)作不易，還望看官點贊收藏打賞，后續(xù)還會更新新的內(nèi)容。