浅谈用二分和三分法解决问题（c++）_三分法c++

问题引入

首先我们来看一下这样一个问题

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

题目描述

有形如：$a{x}^3+b{x}^2+cx+d=0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。

提示：记方程 $f(x)=0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1<x_2$，$f(x_1)\times f(x_2)<0$，则在 $(x_1,x_2)$ 之间一定有一个根。

输入格式

一行，$4$ 个实数 $a,b,c,d$。

输出格式

一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。

样例 #1

样例输入 #1

1 -5 -4 20
1

样例输出 #1

-2.00 2.00 5.00
1

提示

【题目来源】

NOIP 2001 提高组第一题

思路分析

这道题的数据范围相当之小，用暴力就能过

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思考

如果这道题的解空间再开打一下，开到1000,10000，那么暴力就一定过不去了

这时候就需要我们的二分法闪亮登场了

关于二分和三分

二分在下之前写过一篇博客讲解

戳这里

二分解决的问题都有一个共同的性质：单调性

而如果某个问题的解空间是单峰的，不管是向外凸还是向内凹，都可以用另一种算法解决，三分

顾名思义，三分就是一种把解空间分成三段的算法，答案一定在某个段内，时间是$lo{g}_3(n)$但也是$O(log(n))$的算法

简单来说，二分解决零点问题，三分解决极值问题

例题讲解

进击的奶牛

题目描述

Farmer John 建造了一个有 $N$（$2\le N\le 10^5$) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 $x_1,x_2,\cdots ,x_N$（$0\le x_i\le 10^9$）。

他的 $C$（$2\le C\le N$）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入格式

第 $1$ 行：两个用空格隔开的数字 $N$ 和 $C$。

第 $2\sim N+1$ 行：每行一个整数，表示每个隔间的坐标。

输出格式

输出只有一行，即相邻两头牛最大的最近距离。

样例 #1

样例输入 #1

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

样例输出 #1

3
1

思路

二分每一种可能的间隔长度，检查是否符合条件

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

平均数

题目描述

给一个长度为 $n$ 的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度 $\ge m$。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行一个整数 $a_i$，表示序列第 $i$ 个数字。

输出格式

一个整数，表示最大平均数的 $1000$ 倍，如果末尾有小数，直接舍去，不要用四舍五入求整。

样例 #1

样例输入 #1

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

样例输出 #1

6500
1

提示

数据规模与约定

• 对于 $60\%$ 的数据，保证 $m\le n\le 10^4$；
• 对于 $100\%$ 的数据，保证 $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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

Dropping Test

题目描述

在某个课程中，你需要进行 $n$ 次测试。

如果你在共计 $b_i$ 道题的测试 $i$ 上的答对题目数量为 $a_i$，你的累积平均成绩就被定义为

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

给定您的考试成绩和一个正整数 $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$$

输入格式

输入包含多组测试用例，每个测试用例包含三行。

对于每组测试用例，第一行包含两个整数 $n$ 和 $k$。

第二行包含 $n$ 个整数，表示所有的 $a_i$。

第三行包含 $n$ 个整数，表示所有的 $b_i$。

当输入用例 $n=k=0$ 时，表示输入终止，且该用例无需处理。

输出格式

对于每个测试用例，输出一行结果，表示在放弃 $k$ 门成绩的情况下，可能的累积平均成绩最大值。

结果应四舍五入到最接近的整数。

样例 #1

样例输入 #1

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

样例输出 #1

83
100
1
2

提示

数据范围 $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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

【模板】三分 | 函数

题目描述

给定 $n$ 个二次函数 $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)$ 在区间 $[0,1000]$ 上的最小值。

输入格式

输入第一行为正整数 $T$，表示有 $T$ 组数据。

每组数据第一行一个正整数 $n$，接着 $n$ 行，每行 $3$ 个整数 $a,b,c$，用来表示每个二次函数的 $3$ 个系数，注意二次函数有可能退化成一次。

输出格式

每组数据输出一行，表示 $F(x)$ 的在区间 $[0,1000]$ 上的最小值。答案精确到小数点后四位，四舍五入。

样例 #1

样例输入 #1

2
1
2 0 0
2
2 0 0
2 -4 2
1
2
3
4
5
6

样例输出 #1

0.0000
0.5000
1
2

提示

对于 $50\%$ 的数据，$n\le 100$。

对于 $100\%$ 的数据，$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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

Doremy’s IQ

题面翻译

题目描述

哆来咪·苏伊特参加了 $n$ 场比赛。 比赛 $i$ 只能在第 $i$ 天进行。比赛 $i$ 的难度为 $a_i$。最初，哆来咪的 IQ 为 $q$ 。 在第 $i$ 天，哆来咪将选择是否参加比赛 i。只有当她当前的 IQ 大于 $0$ 时，她才能参加比赛。

如果哆来咪选择在第 $i$ 天参加比赛 $i$，则会发生以下情况：

• 如果 $a_i>q$，哆来咪会觉得自己不够聪明，所以 $q$ 将会减 $1$；
• 否则，什么都不会改变。

如果她选择不参加比赛，一切都不会改变。哆来咪想参加尽可能多的比赛。请给哆来咪一个解决方案。

输入格式

第一行包含一个正整数 $t$ ($1\le t\le 10^4$) ，表示测试数据的组数。

第二行包含两个整数 $n$ 和 $q$ ($1\le n\le 10^5$, $1\le q\le 10^9$)，表示比赛次数和哆来咪最开始时的 IQ。

第三行包含 $n$ 个整数 $a_1,a_2\cdots a_n$($1\le a_i\le 10^9$)，表示每场比赛的难度。

数据保证 $n$ 之和不超过 $10^5$。

输出格式

对于每组数据，输出一个二进制字符串 $s$，如果哆来咪应该选择参加比赛 $i$，则 $s_i=1$，否则 $s_i=0$。 字符串中 $1$ 的数量应该尽可能的多，并且当她的 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
2
3
4
5
6
7
8
9
10
11

样例输出 #1

1
11
110
1110
01111
1
2
3
4
5

提示

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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$ 次操作，每次操作可以选定 $\forall i\in [1,n]$ 并将 $a_i$ 赋值为一个 $[1,10^9]$ 的整数。请最大化这个图的直径。

设 $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}{\operatorname{d}(u, v)} $ , where $ \operatorname{d}(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
2
3
4
5
6
7
8
9
10
11
12
13

样例输出 #1

4
168
10
1000000000
9
1000000000
1
2
3
4
5
6

提示

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

The graph built on this array:

$ \operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2 $ and $ \operatorname{d}(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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

这是我的第十二篇文章，如有纰漏也请各位大佬指正

辛苦创作不易，还望看官点赞收藏打赏，后续还会更新新的内容。