你有b块钱，给出n个配件的个子的种类，性能和价格，每种类型的配件买一个，价格不超过b，因为有水桶效应，所以电脑的性能取决于性能最低的配件的性能，问你b块钱配的电脑性能最高有多少。
按照白书的说法，最大值尽量小，最小值尽量大之类的问题一般都可以用二分答案的方法来结局，这道题就是一道典型的最小值最大问题，所以采用二分答案
|
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 |
#include <cstdio>#include <cstring>#include <climits>#include <algorithm>#include <map>#include <vector>#include <string>#include <iostream>using
namespace
std;const
int
maxn = 1005;struct
Component { int
price,quality;};int
cnt,budget,maxquality;map<string,int> id;vector<Component> comp[maxn];void
readin() { char
name[30],power[30]; int
p,q,n; cnt = maxquality = 0; scanf("%d%d\n",&n,&budget); id.clear(); for(int
i = 0;comp[i].size();i++) { comp[i].clear(); } for(int
i = 0;i < n;i++) { scanf("%s%s%d%d",name,power,&p,&q); int
nowid; if(id.count(name)) { nowid = id[name]; } else
{ nowid = cnt++; id[name] = nowid; } comp[nowid].push_back((Component){p,q}); if(q > maxquality) { maxquality = q; } }}bool
ok(int
val) { int
total = 0; for(int
i = 0;i < cnt;i++){ int
cheapest = INT_MAX,m = comp[i].size(); for(int
j = 0;j < m;j++) if(comp[i][j].quality >= val) { cheapest = min(cheapest,comp[i][j].price); } if(cheapest == INT_MAX) return
false; total += cheapest; if(total > budget) { return
false; } } return
true;}void
work() { int
str = 0,end = maxquality,mid; while(str < end) { mid = str + (end - str + 1) / 2; if(ok(mid)) { str = mid; } else
{ end = mid - 1; } } cout << str << endl;}int
main() { int
T; cin >> T; while(T--) { readin(); work(); } return
0;} |
你请来了F个朋友，一起来分N个圆形的派，每个人得到的必须是一块或者是一块派的一部分，而不是几块派拼在一起的，问你每个人最多能得到多大的派
对浮点数的二分，设一个eps，当end-str<eps的时候跳出循环
PS.常量π的值可以用const int PI = acos(-1.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 |
#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <cmath>using
namespace
std;const
int
maxn = 10005;const
double
PI = acos(-1.0);const
double
eps = 1e-5;int
R[maxn];inline
double
square(int
R) { return
PI * R * R;}int
main() { int
T,N,F; scanf("%d",&T); while(T--) { scanf("%d%d",&N,&F); int
maxR = 0; for(int
i = 0;i < N;i++) { scanf("%d",&R[i]); if(R[i] > maxR) { maxR = R[i]; } } double
str = 0,end = square(maxR); while(end - str > eps) { double
mid = (str + end) / 2; int
count = 0; for(int
i = 0;i < N;i++) { count += (int)(square(R[i]) / mid); if(count >= F + 1) { break; } } if(count >= F + 1) { str = mid; } else
{ end = mid; } } printf("%.4lf\n",str); } return
0;} |
有n个人围城一个圈，每个人想拿ri种物品，要求相邻的两个人不能拿一样的，问最少需要多少种物品
当n为偶数的时候非常好处理，只要找到最大的ri+ri-1的和就行了。
当n为奇数的时候可以对所需要的物品数进行二分。
第一个人需要r1件物品，设left[i],right[i]分别为第i个人从1~ri,ri+1~p中拿的物品数目，偶数的人尽量拿前面的，奇数的人尽量拿后面的，那么第n个人必定是尽量拿后面的，此时判断时候和r1冲突即可
|
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 |
#include <cstdio>#include <cstring>#include <algorithm>using
namespace
std;const
int
maxn = 100001;int
r[maxn],n,sum,left[maxn],right[maxn];bool
ok(int
val) { right[0] = 0; left[0] = r[0]; for(int
i = 1;i < n;i++) { if(r[i] > val - left[i - 1] - right[i - 1]) return
false; if((i + 1) % 2 == 0) { left[i] = min(r[i],r[0] - left[i - 1]); right[i] = r[i] - left[i]; } else
{ right[i] = min(r[i],val - r[0] - right[i - 1]); left[i] = r[i] - right[i]; } } return
left[n - 1] == 0;}int
bsearch() { int
L = 1,R = sum; while(L < R) { int
mid = (L + R) / 2; if(ok(mid)) R = mid; else
L = mid + 1; } return
L;}int
main() { while(scanf("%d",&n),n) { sum = 0; for(int
i = 0;i < n;i++) { scanf("%d",&r[i]); sum += r[i]; } if(n % 2 == 1) printf("%d\n",bsearch()); else
{ int
maxd = 0; for(int
i = 0;i < n;i++) { int
f = ((i == 0) ? n - 1 : i - 1); maxd = max(maxd,r[i] + r[f]); } printf("%d\n",maxd); } } return
0;} |
关于二分查找的一些总结：
很多问题都可以用二分来解决，但是根据每次寻找的条件不同，迭代的时候值的变化也会不同,简单总结一下；
1、查找某个元素是否存在
mid = (begin + end) / 2
if(mid < v) begin = mid + 1;
if(mid > v) end = mid – 1;
if(mid == v) return v;
2、查找不小于v的最小值
mid = (end + begin) / 2
if(mid < v) begin = mid + 1; else end = mid;
3、查找大于v的最小值
mid = (end + begin) / 2
if(mid <= v) begin = mid + 1; else end = mid;
3、查找满足条件的v的最小值
mid = (begin + end) / 2
if(ok(mid)) end = mid; else begin = mid – 1;
4、查找满足条件的v的最大值
mid = begin + (end – begin +1) / 2
if(ok(mid)) begin = mid; else end = mid – 1;
可以发现在寻找满足条件的v的最大值的时候mid取值和其他时候不一样，因为在处理两个相邻的数字的时候优先尝试大的那个，mid这样取可以保证一定比begin大，不然有可能会进入死循环
这里顺便总结一下STL中lower_bound和upper_bound 的用法
原型如下
|
1
2
3
4
5
6
7
8 |
template
<class
ForwardIterator, class
T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const
T& val); template
<class
ForwardIterator, class
T, class
Compare> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const
T& val, Compare comp);template
<class
ForwardIterator, class
T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const
T& val); template
<class
ForwardIterator, class
T, class
Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const
T& val, Compare comp); |
函数有两种重载，区别就是多了一个最后的比较函数，默认使用类的operator<，也可以自定义cmp函数，函数接受两个迭代器，分别表示一段范围，注意last表示的是最后一个元素的后一个，返回一个指向所需元素的迭代器，失败了返回last
原文：http://www.cnblogs.com/rolight/p/3541426.html