0%

8.18创新班总结

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

【例题】给定一列长度为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.