C/C++语言100题练习计划 73——Error（二分答案算法实现）

名人说：故立志者，为学之心也；为学者，立志之事也。—— 王阳明
进度：C/C++语言100题练习计划专栏，目前73/100

🥇C/C++语言100题练习专栏计划：目的：巩固练习C/C++语言，增强上机、动手实践能力，交流学习！

一、问题呈现

1.问题描述

Problem Description

刚进入的 Yassin在进行对手机的零件设计，众所周知，测量总是有误差的。现在 Yassin 需要对他的误差进行一定的计算。

现在已经给定的图纸中标定了 n 个零件的大小，我们不妨将其即为a${}_n$ ， 而 Yassin 需要确定一个最小误差 eps, 并用误差范围内的数据来从小到大生产一系列零件。
具体而言，需要确定一个最小的eps, 使得存在这样一个上升的正整数序列b${}_n$，满足对于任意的1<=i<=n，均有|a${}_i$-b${}_i$|<=eps

2.输入输出

Input

第一行一个数字 n，表示图纸的个数。
第二行n个正整数，表示序列a${}_n$ 。

Output

一行一个正整数，为满足条件的最小的误差eps。

3.测试样例

Sample Input

6
7 9 5 1 3 2

Sample Output

6

★提示：
n<=50
数据保证答案小于等于10^9

二、源码实现

//二分查找：在一个已知的有序数据集上进行二分地查找
//二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案
//------------------------------------------------------------
//本题我们可以根据题目的不等式关系，可以看出eps其实是有区间的，
//因此我们可以借助这一点,进行二分答案的实现

#include 
using namespace std;
typedef long long LL;
const LL N = 51;

//n表示图纸的个数,a[N]为序列an,b[N]为正整数上升序列bn
//b_l[N],b_r[N]分别为左、右部分的上升序列bn
LL n,a[N],b_l[N],b_r[N],b[N]; 

bool check(LL eps)
{
	//将b_l,b_r两个数组初始化为0
    memset(b_l,0,sizeof(b_l));
    memset(b_r,0,sizeof(b_r));
    bool flag=true; //利用C++中的bool类型，声明变量flag用作标记。
    
    for(int i=1;i<=n;i++)
    {
    	//最后发现只需要按不等式左半部分执行就可以了，因为bi>=ai-eps同时可以得到eps>=ai-bi 
        b_l[i]=max((LL)0,a[i]-eps); //选出a[i]-eps和0之间更大的那一个赋值给b的左半部分序列
//        b_r[i]=a[i]+eps;
    }
    
    for(int i=1;i<=n;i++)
        b[i]=max(b_l[i],b[i-1]+1); //再将左部分序列和b[i-1]+1的值做比较，选择其中更大的一个赋值给最终的b[i]
        
    for(int i=1;i<=n;i++)
        if(abs(a[i]-b[i])>eps) //因为题目所给不等式abs(a[i]-b[i])<=eps的 如果所得结果有大于的那么返回false
			return false;
    return true;//如果此时没有不符合abs(a[i]-b[i])<=eps的，那么返回true
}

int main()
{
	//输入图纸的个数
    cin>>n;
    //输入序列an
    for(int i=1;i<=n;i++) 
		cin>>a[i];
		
	//二分模板 
    LL l=0,r=1e9;
    while(l<r)
    {
        LL mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    
    //输出满足条件的最小的误差eps 
    cout<<l<<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
51
52
53
54
55
56
57
58
59

★关于二分(查找/答案)算法：

1️⃣二分查找：假设有一升序的数据集合，先找出升序集合中最中间的元素，将数据集合划分为两个子集，将最中间的元素和关键字key进行比较：
如果等于key则返回；如果大于关键字key，则在前一个数据集合中查找，否则在后一个子集中查找，直到找到为止，如果没找到则返回-1；
大家可以看下这张gif图，能够看出二分查找和遍历查找的效率对比效果：

(上图来源网络，侵删)

2️⃣那二分答案呢？

二分查找简单来说的话是在一个已知的有序数据集上进行二分地查找，而二分答案则是答案有一个区间，在这个区间中二分，直到找到最优答案，当然两者主要核心其实是相同的，都是借助二分这样的一个思想。

三、测试结果

6
7 9 5 1 3 2
6
--------------------------------
Process exited after 6.98 seconds with return value 0
请按任意键继续. . .
1
2
3
4
5
6

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ღ( ´･ᴗ･` )比心