Qjbtiger's Home
0%

8.18创新班总结

Posted on Edited on In Views: Valine:

今天，我们学习了二分查找这一主要内容。二分查去找，之前也有涉及到。但是，今天我们对二分查找，进一步的熟悉。

【例题】给定一列长度为N（8.18创新班总结 - 邱俊斌 - 邱俊斌）的从小到大的数列，给定一个数x，问x在数列的下标为多少？

【输入】

5

1 5 7 8 10

8

【输出】

4

【二分查找】二分查找，其实就是把一段数列，分成平均的两段，在对这两个数列进行查找。

由于数列是有序的，因此，一段数列符合如图的规则：

他不见了。

他不见了。

，如果我们要找的书x>mid的话，那么x就只可能在[mid+1,high]这一段之中，不可能在[low,mid]之中了。
以此类推，知道low≥high结束，答案就是low（或是high，因为此时low==high）。

【题目1】已知

他不见了。

,给定time和c，问实数n最大为多少？

【分析】其实，这一道题并不复杂，其实就是枚举n，但是，我们并不是直接枚举，而是二分地枚举。

n一定在【0,2000000000】之间，取

他不见了。

，如果

他不见了。

那么，就一定在区间【low，mid-1】中，反之，在【mid+1，high】。如果刚好等于time，那么就是答案。或者说，只需二分100次，1000次，得到的答案，已经极为接近答案了。

【程序】

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <fstream>
#include <cstdio>
#include <math.h>
using namespace std;

ifstream fin("sorting.in");
//ofstream fout("sorting.out");

int c,tim;
double ans;

void init() {
    fin >> c >> tim;
}

void work() {
    double lo=0, hi=2000000000;//都是double型的

    for (int i=0; i<=100; i++) {//循环100次
        double mid=(lo+hi)/2.0;
        if (c*mid*log2(mid)<=tim)//二分
            lo=mid;
        else
            hi=mid;
    }

    ans=lo;//答案
}

void outit() {
    printf("%.9f\n",ans);//输出要注意，进度为9位
}

int main() {
    freopen("sorting.out","w",stdout);

    init();

    work();

    outit();
    return 0;
}

【题目2】有长度为N的一列，分成M个部分，问数值和最大的那一部分最小为多少？

【输入】

9

10 20 30 40 50 60 70 80 90

3

【输出】

170

【分析】其实，这一道题就是要将数列尽可能的平均分配。其实，这一道题我们也是二分答案。

从区间[0,15000]开始（边界可以设置大一些），二分mid，枚举数列的每一个数，一个个累加。当累加器大于mid时，就说明之前的工作量，是一个部分。这是，累加器等于当前值，继续枚举，依此类推。

如果需要的部分大于M，那么说明，答案应该比mid要大，因此，low=mid+1。反之，high=mid。

【程序】

```c++
#include <fstream>
using namespace std;

ifstream fin("folders.in");
ofstream fout("folders.out");

int N,M,ans;
int data[20];

void init() {
    fin >> N;
    for (int i=0; i!=N; ++i)
        fin >> data[i];
    fin >> M;
}

bool ok(int x) {
    int curw=1;//累计工人数
    int cflo=0;//累加器
    for (int i=0; i!=N; ++i) {
        if (cflo+data[i]>x) {
            if (data[i]>x) return false;
            
            curw++;
            cflo=data[i];
        }
        else
            cflo+=data[i];
    }

    return curw<=M;
}

void work() {
    int lo=0, hi=20000;
    for (; lo<hi; ) {
        int mid=(lo+hi)/2;
        if (ok(mid))//判断mid是否可行；二分
            hi=mid;
        else
            lo=mid+1;
    }

    ans=lo;//答案
}

void outit() {
    fout << ans << endl;
}

int main() {
    init();

    work();

    outit();
    return 0;
}
Thank you so much.