一、 STL函數

• lower_bound()

　　　　試圖在已排序的 [first, last) 中尋找元素 value。返回一個迭代器，指向第一個“不小于 value”的元素，如果 value 大于 [first, last)內的任何一個元素，則返回 last。實際上，它返回“在不破壞順序的情況下，可插入 value 的第一個合適位置”。

• upper_bound()

　　　　試圖在已排序的 [first, last) 中尋找元素 value。返回一個迭代器，如果 value 存在，迭代器將指向最后一個 value 的下一位置。實際上，它會返回“在不破壞順序的情況下，可插入 value 的最后一個合適位置”。也可理解為是第一大于 value 的元素的位置（不存在則返回 last）。

• binary_search()

　　　　返回值為 Bool 類型，如果 [first, last)內有等同于value的元素，便返回 true，否則返回 false。

• equal_range()

　　　　返回一個pair，其 first 成員是 lower_bound 返回的迭代器，second 成員返回的是 upper_bound 返回的迭代器。

二、二分搜索實現及分析

　　二分搜索可分為整數型和小數型，其中整數型最為麻煩，邊界條件、停止條件、區間初始化等容易搞混。

　　整數二分

?　　以實現 lower_bound 為例，給定長度為$n$的單調不下降數列$a_{0},\cdots,a_{n-1}$和一個數$k$，求滿足$a_{i}\geqslant k$的最小的$i$。不存在的情況下輸出$n$。

1 int n, k; 2 int a[MAX_N]; 3 4 void solve() { 5 int lb = -1, ub = n; 6 7 while (ub - lb > 1) { 8 int mid = lb + (ub - lb) / 2; 9 if (a[mid] >= k) { 10 // 如果mid滿足條件，則解的存在范圍變為(lb, mid] 11 ub = mid; 12 } else { 13 // 如果mid不滿足條件，則解的存在范圍變為(mid, ub] 14 lb = mid; 15 } 16 } 17 18 print("%d\n", ub) 19 }

　　分析：1. n = 0 那么此時 lb = -1，ub = n = 0，跳過 while 循環，輸出 ub = n = 0，正確

　　　　　2. n = 1 那么此時 lb = -1，ub = n = 1，進入 while 循環， mid = 0。假如$a[0] \geqslant k$，那么 ub = 0，輸出 ub = 0，否則 lb = 0，輸出 ub = 0。

　　　　　3. 若 i 應為 0（即a[0] = k，數組左端點），那么 ub 會一直向左收縮（此過程中 lb 不變），直到 mid = 0，從而 ub = mid = 0。輸出 ub = 0.

　　　　　4. 若 i 應為 n - 1（即a[n-1] = k，數組右端點），那么 lb 會一直向右收縮（此過程中 ub 不變），直到 lb = n - 2，lb + 2 = ub，此時 mid = n - 1，a[mid] == k, ub = n - 1，下一循環時條件不成立，輸出 ub = n - 1.

　　　　　5. 若 i 應為 n（即數組中無 k），那么 lb 會一直向右收縮（此過程 ub 不變），直到 lb = n - 1，循環條件不成立，輸出 ub = n。

　　　　由上述分析可知，可解范圍一直為 (lb, ub]。lb用來不斷縮小范圍。

　　小數二分

　　在使用二分搜索時，有必要設置合理的結束條件來滿足精度的要求。1次循環可以把區間的范圍縮小一半，100次的循環控制可以達到$100^{-30}$的精度范圍。除此之外，可以把停止條件設置為$(ub-lb)>EPS$，指定一個區間的大小，要注意的是如果EPS取得太小，可能會因為浮點小數的精度問題而導致死循環，所以推薦第一種停止條件。

三、二分搜索思想的擴展

　　分析 lower_bound() 函數，其搜索也可轉化為“求滿足某個條件$C(x)$的最小的$x$"這一問題。而$C(x)$即為$a_{i}\geqslant?k$。對于任意滿足$C(x)$的$x$，如果所有的${x}'\geqslant?x$也滿足$C({x}')$的話，我們就可以用二分搜索來求得最小的$x$。

　　首先我們將區間的左端點初始化為不滿足$C(x)$的值，右端點初始化為滿足$C(x)$的值，然后每次取中點 mid，判斷$C(mid)$是否滿足并縮小范圍，直到 (lb, ub] 足夠小了位置，最后 ub 就是要求的最小值。最大化的問題也可以用同樣的方法。

　　1. 假定一個解并判斷是否可行

?POJ No. 1064 Cable master

DescriptionInhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it. To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible. The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled. You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces. InputThe first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point. OutputWrite to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point. If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes). Sample Input4 11 8.02 7.43 4.57 5.39 Sample Output2.00

　　　令：條件$C(x):=$可以得到$K$條長度為$x$的繩子

　　　則問題變為求滿足$C(x)$條件的最大的$x$。首先考慮區間的初始化問題。

　　　lb = 0；ub = INF

　　　長度的有效性肯定是不能超過$L_{i}$。那么我們直接設置這個值為INF(INT_MAX)。最小不能為0。

　　　現在的問題是是否可以高效的判斷$C(x)$。由于長度為$L_{i}$的繩子最多可以切出$floor(L_{i} / x)$段長度為$x$繩子，因此

　　　$C(x)=$($floor(L_{i} / x)$的總和是否大于或等于$K$)。

　　注意：此題為小數二分，較整數二分容易些；

　　　　　此題求的是滿足條件的最大x，所以當滿足條件時，lb = mid。所以才能求得最大值。

　　　　　結果顯示2位小數，且不可四舍五入，處理方法為先乘上10的要顯示的位數次方，取floor后再除以剛才乘上的因子。例如0.366，四舍五入為0.37，0.366 * 100 = 36.6，floor(36.6) = 36.， 36. / 100 = 0.36。?

1 #include <iostream> 2 #include <vector> 3 #include <math.h> 4 #include <limits.h> 5 using namespace std; 6 7 const int MAX = 100000 + 5; 8 int N = 0, K = 0; 9 double length[MAX]; 10 11 bool C(double x) { 12 int num = 0; 13 for (int i = 0; i < N; ++i) { 14 num += (int)(length[i] / x); 15 } 16 return num >= K; 17 } 18 int main(){ 19 cin >> N >> K; 20 for (int i = 0; i < N; ++i) { 21 cin >> length[i]; 22 } 23 24 double lb = 0, ub = INT_MAX; 25 for (int i = 0; i < 100; ++i) { 26 double mid = (ub - lb) / 2 + lb; 27 if (C(mid)) 28 lb = mid; 29 else 30 ub = mid; 31 } 32 33 printf("%.2f\n", floor(lb * 100) / 100); 34 system("pause"); 35 return 0; 36 } View Code

?

　　2.最大化最小值 or 最小化最大值

POJ No.2456 Aggressive cows

DescriptionFarmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000). His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance? Input* Line 1: Two space-separated integers: N and C * Lines 2..N+1: Line i+1 contains an integer stall location, xi Output* Line 1: One integer: the largest minimum distance Sample Input5 3 1 2 8 4 9 Sample Output3 HintOUTPUT DETAILS: FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3. Huge input data,scanf is recommended. View Code

　　分析問題，使間距最近的兩頭牛的間距最大化，那么直接方法是遍歷間距 d。

　　定義 $C(d):=$可以安排牛的位置使得最近的兩頭牛的距離不小于d，問題變為求滿足$C(d)$的最大的 d。

　　換一種表述方式，最近的間距不小于 d 也可以表述為所有牛的間距都不小于 d，因此

　　定義 $C(d):=$可以安排牛的位置使得任意的牛的間距都不小于d。

　　貪心法求解

• 對牛舍的位置 pos 進行排序
• 把第一頭牛放入 pos[0] 的牛舍
• 如果第 i 頭牛放入了 pos[j] 的話，第 i+1 頭牛就要放入滿足$pos[j] + d\leqslant pos[k]$的最小的 pos[k]。

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 using namespace std; 6 7 const int MAX = 100000 + 5; 8 int N, C; 9 int pos[MAX]; 10 11 bool check(int d) { 12 int pre = 0; // 第一頭牛放在 pos[0] 位置 13 // 遍歷剩下的 C-1 頭牛，即枚舉所有牛的間距 14 for (int i = 1; i < C; ++i) { 15 int cur = pre + 1; 16 while (cur < N && pos[cur] - pos[pre] < d) { 17 ++cur; 18 } 19 if (cur == N) 20 return false; 21 pre = cur; 22 } 23 return true; 24 } 25 int main() { 26 cin >> N >> C; 27 for (int i = 0; i < N; ++i) { 28 cin >> pos[i]; 29 } 30 std::sort(pos, pos + N); 31 int lb = 0, ub = INT_MAX; // 解范圍的初始化[lb, ub) 32 while (ub - lb > 1) { 33 int mid = (ub - lb) / 2 + lb; 34 if (check(mid)) 35 lb = mid; 36 else 37 ub = mid; 38 } 39 printf("%d\n", lb); 40 return 0; 41 } View Code

?

?POJ No.3258?River Hopscotch

DescriptionEvery year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L).To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).FJ wants to know exactly how much he can increase the shortest distance *before* he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.InputLine 1: Three space-separated integers: L, N, and M Lines 2..N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position. OutputLine 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks Sample Input25 5 2 2 14 11 21 17 Sample Output4 HintBefore removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25). View Code

　　這道題與POJ 2456非常相似，這道題是拿走幾個位置，而2456是選幾個位置放入，實際上是一樣的。

　　定義$C(x)=$在丟棄石子數量不超過 M 的前提下，使得任意石子的間距都不小于d。

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 using namespace std; 6 7 const int MAX = 50000 + 5; 8 int length, n, m; 9 int dist[MAX]; 10 11 bool check(int d) { 12 int pre = 0, drop = 0; 13 for (int i = 1; i <= n + 1; ++i) { 14 if (dist[i] - dist[pre] < d) { 15 ++drop; 16 } 17 else { 18 pre = i; 19 } 20 } 21 22 return drop <= m; 23 } 24 int main() { 25 cin >> length >> n >> m; 26 for (int i = 1; i <= n; ++i) { 27 cin >> dist[i]; 28 } 29 dist[0] = 0; 30 dist[n + 1] = length; 31 sort(dist, dist + n + 1); 32 33 int lb = 0, ub = INT_MAX; 34 while (ub - lb > 1) { 35 double mid = (ub - lb) / 2 + lb; 36 if (check(mid)) 37 lb = mid; 38 else 39 ub = mid; 40 } 41 printf("%d\n", lb); 42 system("pause"); 43 return 0; 44 } View Code

?

POJ No.3273?Monthly Expense

DescriptionFarmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ moneyi ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit. InputLine 1: Two space-separated integers: N and M Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day OutputLine 1: The smallest possible monthly limit Farmer John can afford to live with. Sample Input7 5 100 400 300 100 500 101 400 Sample Output500 HintIf Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit View Code

　　題目的意思是將一組N個數據分成M個連續的包，要求每個包容量的最小值 如果分成1份的話，這個包的容量就是所有數據之和SUM 如果分成N份的話，這個包的容量就是N個數字中的最大元素MAX 于是我們要求的就是[MAX,SUM]中某一值K。

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 using namespace std; 6 7 const int MAX = 100000 + 5; 8 int N, M; 9 int money[MAX]; 10 11 bool check(int d) { 12 int cnt = 0; 13 for (int i = 0; i < N; ++i) { 14 int sum = money[i]; 15 while (i + 1 < N && sum + money[i + 1] <= d) 16 sum += money[++i]; 17 ++cnt; 18 } 19 return cnt <= M; 20 } 21 int main() { 22 scanf("%d%d", &N, &M); 23 int lb = 0, ub = 0; 24 for (int i = 0; i < N; ++i) { 25 scanf("%d", &money[i]); 26 ub += money[i]; 27 lb = max(lb, money[i]); 28 } 29 --lb; // 解的范圍(lb, ub] 30 while (ub - lb > 1) { 31 int mid = (ub - lb) / 2 + lb; 32 if (check(mid)) 33 ub = mid; 34 else 35 lb = mid; 36 } 37 printf("%d\n", ub); 38 system("pause"); 39 return 0; 40 } View Code

　　注意的是此解里 lb 初始化為 max - 1，ub初始化為 sum，經測試，ub 初始化為 INT_MAX也可以，不過 lb不能直接初始化為 -1 或 0。因為 lb 初始化為 max - 1 避免了在check過程程中檢查 單個元素的值是否超過了 mid，因為如果超過了，無論如何是不能按照 mid 劃分的。所以如果非要將 lb 初始化為 -1 或 0，那么就必須在 check() 中檢查單個元素的值是否超過了給定值。

　　lb 初始化為 -1 的版本：

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 using namespace std; 6 7 const int MAX = 100000 + 5; 8 int N, M; 9 int money[MAX]; 10 11 bool check(int d) { 12 int cnt = 0; 13 for (int i = 0; i < N; ++i) { 14 if (money[i] > d) return false; 15 int sum = money[i]; 16 while (i + 1 < N && sum + money[i + 1] <= d) 17 sum += money[++i]; 18 ++cnt; 19 } 20 return cnt <= M; 21 } 22 int main() { 23 scanf("%d%d", &N, &M); 24 int lb = 0, ub = 0; 25 for (int i = 0; i < N; ++i) { 26 scanf("%d", &money[i]); 27 ub += money[i]; 28 lb = max(lb, money[i]); 29 } 30 lb = -1; 31 while (ub - lb > 1) { 32 int mid = (ub - lb) / 2 + lb; 33 if (check(mid)) 34 ub = mid; 35 else 36 lb = mid; 37 } 38 printf("%d\n", ub); 39 system("pause"); 40 return 0; 41 } View Code

?

POJ No.3104?Drying

DescriptionIt is very hard to wash and especially to dry clothes in winter. But Jane is a very smart girl. She is not afraid of this boring process. Jane has decided to use a radiator to make drying faster. But the radiator is small, so it can hold only one thing at a time.Jane wants to perform drying in the minimal possible time. She asked you to write a program that will calculate the minimal time for a given set of clothes.There are n clothes Jane has just washed. Each of them took ai water during washing. Every minute the amount of water contained in each thing decreases by one (of course, only if the thing is not completely dry yet). When amount of water contained becomes zero the cloth becomes dry and is ready to be packed.Every minute Jane can select one thing to dry on the radiator. The radiator is very hot, so the amount of water in this thing decreases by k this minute (but not less than zero — if the thing contains less than k water, the resulting amount of water will be zero).The task is to minimize the total time of drying by means of using the radiator effectively. The drying process ends when all the clothes are dry.InputThe first line contains a single integer n (1 ≤ n ≤ 100 000). The second line contains ai separated by spaces (1 ≤ ai ≤ 109). The third line contains k (1 ≤ k ≤ 109).OutputOutput a single integer — the minimal possible number of minutes required to dry all clothes.Sample Inputsample input #1 3 2 3 9 5sample input #2 3 2 3 6 5 Sample Outputsample output #1 3sample output #2 2 View Code

　　對于某一件衣服 i，假設其使用?radiator x 分鐘，那么其自然晾干需要 mid - x 分鐘，則若要晾干此件衣服，需滿足 $ x\times k + (mid - x) \ geqslant water[i]$，即 $x \geqslant (water[i] - d) / ( k - 1)$。這里需注意的是，假如需要烘干 5.1分鐘，那么實際上占用了 ceil(5.1) = 6分鐘。將所有衣服的最少烘干時間加起來，如果不大于 mid 時間，則能全部晾干。

另外需注意 k = 1的情況，此時 k - 1 = 0，需作特殊情況討論。實際上若 k = 1，所需時間即為所有衣服的水量總和，直接返回 ub 即可。

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 const int MAX = 100000 + 5; 9 int n, k; 10 long long water[MAX]; 11 12 bool check(int d) { 13 long long cnt = 0; 14 for (int i = 0; i < n; ++i) { 15 if (water[i] > d) { 16 cnt += ceil((water[i] - d)*1.0 / (k - 1)); 17 // 亦可 cnt += (water[i] - d - 1) / (k - 1) + 1; 18 } 19 } 20 return cnt <= d; 21 } 22 int main() { 23 while (scanf("%d", &n) != EOF){ 24 long long lb = -1, ub = 0; 25 for (int i = 0; i < n; ++i) { 26 scanf("%lld", &water[i]); 27 ub = max(ub, water[i]); 28 } 29 scanf("%lld", &k); 30 if (k <= 1) { 31 printf("%d\n", ub); 32 continue; 33 } 34 while (ub - lb > 1) { 35 long long mid = (ub - lb) / 2 + lb; 36 if (check(mid)) 37 ub = mid; 38 else 39 lb = mid; 40 } 41 printf("%lld\n", ub); 42 } 43 system("pause"); 44 return 0; 45 } View Code

?

POJ No.3045?Cow Acrobats

DescriptionFarmer John's N (1 <= N <= 50,000) cows (numbered 1..N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging from the trapeze (and their last attempt at firing a cow out of a cannon met with a dismal failure). Thus, they have decided to practice performing acrobatic stunts. The cows aren't terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves ithin this stack. Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows. Input* Line 1: A single line with the integer N. * Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i. Output* Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk. Sample Input3 10 3 2 5 3 3 Sample Output2 HintOUTPUT DETAILS: Put the cow with weight 10 on the bottom. She will carry the other two cows, so the risk of her collapsing is 2+3-3=2. The other cows have lower risk of collapsing. View Code

　　這個題想來想去不會做，其實用不到二分搜索，有些貪心思想在里面。所以遇到最大化最小值或者最小化最大值的題目時，不一定非得要用到二分。

　　對于第 i 個 和第 j 個，假如 i 位于 j 之上為最優，那么需滿足 前者的最大損失小于后者的最大損失，即 $max(-s_{i}, w_{i} - s_{j})< max(-s_{j}, w_{j} - s_{i})$。

　　對輸入數組進行排序即可。

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 const int MAX = 100000 + 5; 9 int n, k; 10 struct Cow { 11 int w, s; 12 13 bool operator<(const Cow &c) const { 14 return max(-s, w - c.s) < max(-c.s, c.w - s); 15 } 16 } cows[MAX]; 17 18 int main() { 19 scanf("%d", &n); 20 for (int i = 0; i < n; ++i) { 21 scanf("%d%d", &cows[i].w, &cows[i].s); 22 } 23 sort(cows, cows + n); 24 int risk = -cows[0].s; 25 int sum = cows[0].w; 26 for (int i = 1; i < n; ++i) { 27 risk = max(risk, sum - cows[i].s); 28 sum += cows[i].w; 29 } 30 printf("%d\n", risk); 31 return 0; 32 } View Code

　

　　3.最大化平均值

有 $n$個物品的重量和價值分別是$w_{i}$和$v_{i}$。從中選出$k$個物品使得單位重量的價值最大

限制條件 ：$1\leqslant k \leqslant n \leqslant 10^{4}$;?$1\leqslant w_{i}, v_{i} \leqslant 10^{6}$

輸入?

n = 3

k = 2

(w, v) = { (2, 2), (5, 3), (2, 1) }

輸出

0.75 （如果選 0 號和 2 號物品，平均價值是 (2 + 1) / (2 + 2) = 0.75)

　　定義?$C(x):=$可以選擇使得單位重量的價值不小于$x$

　　原問題變換為求滿足$C(x)$的最大的 x。剩下的問題就是如何判斷$C(x)$是否可行了。

　　假設我們選定了某個物品的集合$S$，那么它們的單位重量的價值是

　　$\sum\limits_{i\in S}v_{i} / \sum\limits_{i\in S}w_{i}$

　　因此問題就變成了判斷是否存在$S$滿足下面的條件

　　$\sum\limits_{i\in S}v_{i} / \sum\limits_{i\in S}w_{i} \geqslant x$

　　不等式變形得到

　　$\sum\limits_{i\in S}(v_{i} - x\times w_{i}) \geqslant 0$

　　因此可以對$(v_{i} -?x\times w_{i})$的值進行排序貪心地進行選取

　　定義 $C(x)=$($(v_{i} -?x\times w_{i})$從大到小排列中的前$k$個和不小于0）

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 using namespace std; 6 7 const int MAX = 100000 + 5; 8 int n, k; 9 int w[MAX], v[MAX]; 10 double tmp[MAX]; // v - x * w 11 12 bool check(double x) { 13 for (int i = 0; i < n; ++i) { 14 tmp[i] = v[i] - x * w[i]; 15 } 16 sort(tmp, tmp + n); 17 18 // 計算從大到小前 k 個數的和 19 double sum = 0; 20 for (int i = 0; i < k; ++i) { 21 sum += tmp[n - 1 - i]; 22 } 23 return sum >= 0; 24 } 25 int main() { 26 cin >> n >> k; 27 for (int i = 0; i < n; ++i) { 28 cin >> w[i] >> v[i]; 29 } 30 31 double lb = 0, ub = INT_MAX; 32 for (int i = 0; i < 100; ++i) { 33 double mid = (ub - lb) / 2 + lb; 34 if (check(mid)) 35 lb = mid; 36 else 37 ub = mid; 38 } 39 printf("%.2f\n", lb); 40 system("pause"); 41 return 0; 42 } View Code

?

POJ No.2976?Dropping tests?

DescriptionIn a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be.Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .InputThe input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.OutputFor each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.Sample Input3 1 5 0 2 5 1 6 4 2 1 2 7 9 5 6 7 9 0 0 Sample Output83 100 HintTo avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997). View Code

　　網上一查，結果時 01分數規劃問題，不懂。。。先mark，畢竟已經過了acmer的年紀。關于解，查看 url

　　此題就是將數組 c[i] = a[i] - x * b[i]? 從大到小排序，取前 n - k個的和，看與0的大小關系。實際上和上一題一模一樣。

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 const int MAX = 1000 + 5; 9 const double eps = 1e-7; 10 int n, k; 11 long long a[MAX], b[MAX]; 12 double c[MAX]; 13 14 bool check(double x) { 15 for (int i = 0; i < n; ++i) { 16 c[i] = a[i] - x * b[i]; 17 } 18 sort(c, c + n); 19 double sum = 0; 20 // 丟棄 k 個，留下 n - k 個 21 for (int i = 0; i < n - k; ++i) { 22 sum += c[n - 1 - i]; 23 } 24 return sum >= 0; 25 } 26 27 int main() { 28 while (scanf("%d%d", &n, &k) != EOF && (n || k)) { 29 for (int i = 0; i < n; ++i) { 30 scanf("%lld", &a[i]); 31 } 32 for (int i = 0; i < n; ++i) { 33 scanf("%lld", &b[i]); 34 } 35 double lb = 0.0, ub = 1.0; 36 while (ub - lb > eps) { 37 double mid = (ub - lb) / 2 + lb; 38 if (check(mid)) 39 lb = mid; 40 else 41 ub = mid; 42 } 43 printf("%0.0f\n", lb * 100); 44 } 45 46 system("pause"); 47 return 0; 48 } View Code

?

POJ No.3111?K Best

DescriptionDemy has n jewels. Each of her jewels has some value vi and weight wi.Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep k best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels S = {i1, i2, …, ik} as.Demy would like to select such k jewels that their specific value is maximal possible. Help her to do so.InputThe first line of the input file contains n — the number of jewels Demy got, and k — the number of jewels she would like to keep (1 ≤ k ≤ n ≤ 100 000).The following n lines contain two integer numbers each — vi and wi (0 ≤ vi ≤ 106, 1 ≤ wi ≤ 106, both the sum of all vi and the sum of all wi do not exceed 107).OutputOutput k numbers — the numbers of jewels Demy must keep. If there are several solutions, output any one.Sample Input3 2 1 1 1 2 1 3 Sample Output1 2 View Code

　　和上面兩題一樣，不過需要將 pos 同時記錄下來。

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 const int MAX = 100000 + 5; 9 const double eps = 1e-7; 10 int n, k; 11 12 struct Node { 13 double v, w, t; 14 int id; 15 bool operator<(const Node &other) const { 16 return t > other.t; 17 } 18 } node[MAX]; 19 20 bool check(double x) { 21 for (int i = 0; i < n; ++i) { 22 node[i].t = node[i].v - x * node[i].w; 23 } 24 sort(node, node + n); 25 double sum = 0; 26 27 for (int i = 0; i < k; ++i) { 28 sum += node[i].t; 29 } 30 return sum >= 0; 31 } 32 33 int main() { 34 while (scanf("%d%d", &n, &k) != EOF && (n || k)) { 35 double lb = 0.0, ub = INT_MAX; 36 for (int i = 0; i < n; ++i) { 37 scanf("%lf%lf", &node[i].v, &node[i].w); 38 node[i].id = i + 1; 39 } 40 while (ub - lb > eps) { 41 double mid = (ub - lb) / 2 + lb; 42 if (check(mid)) 43 lb = mid; 44 else 45 ub = mid; 46 } 47 48 for (int i = 0; i < k; ++i) { 49 if (i > 0) 50 printf(" "); 51 printf("%d", node[i].id); 52 } 53 printf("\n"); 54 } 55 return 0; 56 } View Code

?

　　4. 查找第K大的值

POJ? No.3579 Median

DescriptionGiven N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.InputThe input consists of several test cases. In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, ... , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )OutputFor each test case, output the median in a separate line.Sample Input4 1 3 2 4 3 1 10 2 Sample Output1 8 View Code

　　此題的本質即判斷有序序列中二分找出中位數。假如序列長 n，則中位數是第$(n+1)/2)$個數，位置下標為$(n+1)/2 - 1$。

　　先觀察無重復元素的有序序列第k大問題。當序列中沒有重復元素時，第k大元素左邊有k-1個元素，右邊有n-k個元素。

　　推廣到含重復元素的情況時，第k大元素值(val)有以下性質。

• 　大于等于 val 的元素個數應大于$n-k$個。求最大 val。
• 　大于?val?的元素個數應小于等于$n-k$個。求最小 val。
• ? ?小于等于?val?的元素個數應大于$k-1$個。求最小 val。
• ? ?小于?val?的元素個數應小于等于$k-1$個。求最大 val。

　　假設中位數的值為 val。對于無重復元素的有序序列，中位數為第$(n+1)/2$大元素。其左邊應該有$(n-1)/2$個元素，右邊有$n/2$個元素。那么其性質為

• 　大于等于 val 的元素個數應大于$n/2$個。求最大 val。
• 　大于?val?的元素個數應小于等于$n/2$個。求最小 val。
• ? ?小于等于?val?的元素個數應大于$(n-1)/2$個。求最小 val。
• ? ?小于?val?的元素個數應小于等于$(n-1)/2$個。求最大 val。

　　下面給出四種情況的代碼

Condition 1

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 const int MAX = 100000 + 5; 9 int N; 10 long long m; 11 int x[MAX]; 12 13 bool check(int mid) { 14 long long cnt = 0; 15 for (int i = 0; i < N; ++i) { 16 // cnt 記錄了a[j]-a[i]>=mid的a[j]的個數 17 cnt += x + N - lower_bound(x + i + 1, x + N, mid + x[i]); 18 19 } 20 return cnt > m; // 說明 mid 太小 21 } 22 23 int main() { 24 while (scanf("%d", &N) != EOF) { 25 int lb = 0, ub = INT_MAX; 26 for (int i = 0; i < N; ++i) { 27 scanf("%d", &x[i]); 28 } 29 sort(x, x + N); 30 m = (N * (N - 1) / 2) / 2; 31 32 while (ub - lb > 1) { 33 int mid = (ub - lb) / 2 + lb; 34 if (check(mid)) 35 lb = mid; 36 else 37 ub = mid; 38 } 39 printf("%d\n", lb); 40 } 41 system("pause"); 42 return 0; 43 } View Code

Condition 2

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 const int MAX = 100000 + 5; 9 int N; 10 long long m; 11 int x[MAX]; 12 13 bool check(int mid) { 14 long long cnt = 0; 15 for (int i = 0; i < N; ++i) { 16 // cnt 記錄了a[j]-a[i]>mid的a[j]的個數 17 cnt += x + N - upper_bound(x + i, x + N, mid + x[i]); 18 } 19 return cnt <= m; // 說明 mid 太大 20 } 21 22 int main() { 23 while (scanf("%d", &N) != EOF) { 24 int lb = 0, ub = INT_MAX; 25 for (int i = 0; i < N; ++i) { 26 scanf("%d", &x[i]); 27 } 28 sort(x, x + N); 29 m = (N * (N - 1) / 2 ) / 2; 30 31 while (ub - lb > 1) { 32 int mid = (ub - lb) / 2 + lb; 33 if (check(mid)) 34 ub = mid; 35 else 36 lb = mid; 37 } 38 printf("%d\n", ub); 39 } 40 return 0; 41 } View Code

Condition 3

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 const int MAX = 100000 + 5; 9 int N; 10 long long m; 11 int x[MAX]; 12 13 bool check(int mid) { 14 long long cnt = 0; 15 for (int i = 0; i < N; ++i) { 16 // cnt 記錄了a[j]-a[i]<=mid的a[j]的個數 17 cnt += upper_bound(x + i, x + N, mid + x[i]) - 1 - (x + i); 18 } 19 return cnt > m; // 說明 mid 太大 20 } 21 22 int main() { 23 while (scanf("%d", &N) != EOF) { 24 int lb = 0, ub = INT_MAX; 25 for (int i = 0; i < N; ++i) { 26 scanf("%d", &x[i]); 27 } 28 sort(x, x + N); 29 m = (N * (N - 1) / 2 - 1) / 2; 30 31 while (ub - lb > 1) { 32 int mid = (ub - lb) / 2 + lb; 33 if (check(mid)) 34 ub = mid; 35 else 36 lb = mid; 37 } 38 printf("%d\n", ub); 39 } 40 return 0; 41 } View Code

Condition 4

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 const int MAX = 100000 + 5; 9 int N; 10 long long m; 11 int x[MAX]; 12 13 bool check(int mid) { 14 long long cnt = 0; 15 for (int i = 0; i < N; ++i) { 16 // cnt 記錄了a[j]-a[i]<mid的a[j]的個數 17 cnt += lower_bound(x + i + 1, x + N, mid + x[i]) - 1 - (x + i); 18 } 19 return cnt <= m; // 說明 mid 太小 20 } 21 22 int main() { 23 while (scanf("%d", &N) != EOF) { 24 int lb = 0, ub = INT_MAX; 25 for (int i = 0; i < N; ++i) { 26 scanf("%d", &x[i]); 27 } 28 sort(x, x + N); 29 m = (N * (N - 1) / 2 - 1) / 2; 30 31 while (ub - lb > 1) { 32 int mid = (ub - lb) / 2 + lb; 33 if (check(mid)) 34 lb = mid; 35 else 36 ub = mid; 37 } 38 printf("%d\n", lb); 39 } 40 return 0; 41 } View Code

?

POJ No.3685 Matrix

DescriptionGiven a N × N matrix A, whose element in the i-th row and j-th column Aij is an number that equals i2 + 100000 × i + j2 - 100000 × j + i × j, you are to find the M-th smallest element in the matrix.InputThe first line of input is the number of test case. For each test case there is only one line contains two integers, N(1 ≤ N ≤ 50,000) and M(1 ≤ M ≤ N × N). There is a blank line before each test case.OutputFor each test case output the answer on a single line.Sample Input121 12 12 22 32 43 13 23 83 95 15 255 10 Sample Output3 -99993 3 12 100007 -199987 -99993 100019 200013 -399969 400031 -99939 View Code

?　　觀察公式$i^{2} + 100000\times i + j^{2} -?100000 \times j + i \times j$，當固定 j 時，可以發現該函數關于 i 時遞增的，所以在第 j 列中，函數值是從上往下遞增的，這符合二分搜索的條件。先二分枚舉 value，如果小于 value 的元素個數小于 M，說明該 value 太小。M-th 小的數為排序后數組的第M個數，那么在無重復元素的情況下小于第M個元素值的元素個數應該小于M。另外在check value時，也需要二分枚舉行數，暴力枚舉會超時。

　　定義$C(x)=$數組中元素對應的函數值小于 value的個數小于 M 個。求最大value。

1 #include <iostream> 2 #include <vector> 3 #include <limits.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 8 long long num, N, M; 9 10 long long func(long long i, long long j) { 11 return i*i + 100000 * i + j * j - 100000 * j + i * j; 12 } 13 14 bool check(long long val) { 15 long long cnt = 0; 16 for (int j = 1; j < N + 1; ++j) { // 枚舉列 17 int lb = 0, ub = N + 1; 18 while (ub - lb > 1) { // 枚舉行 19 int mid = (ub - lb) / 2 + lb; 20 if (func(mid, j) < val) 21 lb = mid; 22 else 23 ub = mid; 24 } 25 cnt += lb; 26 } 27 return cnt < M; 28 } 29 30 int main() { 31 scanf("%lld", &num); 32 while (num--) { 33 scanf("%lld%lld", &N, &M); 34 long long lb = -100000 * N, ub = N * N + 100000 * N + N * N + N * N; 35 36 while (ub - lb > 1) { 37 long long mid = (ub - lb) / 2 + lb; 38 if (check(mid)) 39 lb = mid; 40 else 41 ub = mid; 42 } 43 printf("%lld\n", lb); 44 } 45 system("pause"); 46 return 0; 47 } View Code

?

　　5. 最小化第K大的值

POJ No.2010?Moo University - Financial Aid

DescriptionBessie noted that although humans have many universities they can attend, cows have none. To remedy this problem, she and her fellow cows formed a new university called The University of Wisconsin-Farmside,"Moo U" for short. Not wishing to admit dumber-than-average cows, the founders created an incredibly precise admission exam called the Cow Scholastic Aptitude Test (CSAT) that yields scores in the range 1..2,000,000,000. Moo U is very expensive to attend; not all calves can afford it.In fact, most calves need some sort of financial aid (0 <= aid <=100,000). The government does not provide scholarships to calves,so all the money must come from the university's limited fund (whose total money is F, 0 <= F <= 2,000,000,000). Worse still, Moo U only has classrooms for an odd number N (1 <= N <= 19,999) of the C (N <= C <= 100,000) calves who have applied.Bessie wants to admit exactly N calves in order to maximize educational opportunity. She still wants the median CSAT score of the admitted calves to be as high as possible. Recall that the median of a set of integers whose size is odd is the middle value when they are sorted. For example, the median of the set {3, 8, 9, 7, 5} is 7, as there are exactly two values above 7 and exactly two values below it. Given the score and required financial aid for each calf that applies, the total number of calves to accept, and the total amount of money Bessie has for financial aid, determine the maximum median score Bessie can obtain by carefully admitting an optimal set of calves. Input* Line 1: Three space-separated integers N, C, and F * Lines 2..C+1: Two space-separated integers per line. The first is the calf's CSAT score; the second integer is the required amount of financial aid the calf needs Output* Line 1: A single integer, the maximum median score that Bessie can achieve. If there is insufficient money to admit N calves,output -1. Sample Input3 5 70 30 25 50 21 20 20 5 18 35 30 Sample Output35 HintSample output:If Bessie accepts the calves with CSAT scores of 5, 35, and 50, the median is 35. The total financial aid required is 18 + 30 + 21 = 69 <= 70. View Code

?

POJ No.3662?Telephone Lines

DescriptionFarmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John's property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart. The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.Determine the minimum amount that Farmer John must pay.Input* Line 1: Three space-separated integers: N, P, and K * Lines 2..P+1: Line i+1 contains the three space-separated integers: Ai, Bi, and LiOutput* Line 1: A single integer, the minimum amount Farmer John can pay. If it is impossible to connect the farm to the phone company, print -1.Sample Input5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6 Sample Output4 View Code

?

　　6.其他

POJ No.1759 Garland?

DescriptionThe New Year garland consists of N lamps attached to a common wire that hangs down on the ends to which outermost lamps are affixed. The wire sags under the weight of lamp in a particular way: each lamp is hanging at the height that is 1 millimeter lower than the average height of the two adjacent lamps. The leftmost lamp in hanging at the height of A millimeters above the ground. You have to determine the lowest height B of the rightmost lamp so that no lamp in the garland lies on the ground though some of them may touch the ground. You shall neglect the lamp's size in this problem. By numbering the lamps with integers from 1 to N and denoting the ith lamp height in millimeters as Hi we derive the following equations: H1 = A Hi = (Hi-1 + Hi+1)/2 - 1, for all 1 < i < N HN = B Hi >= 0, for all 1 <= i <= N The sample garland with 8 lamps that is shown on the picture has A = 15 and B = 9.75. InputThe input file consists of a single line with two numbers N and A separated by a space. N (3 <= N <= 1000) is an integer representing the number of lamps in the garland, A (10 <= A <= 1000) is a real number representing the height of the leftmost lamp above the ground in millimeters. OutputWrite to the output file the single real number B accurate to two digits to the right of the decimal point representing the lowest possible height of the rightmost lamp. Sample Input692 532.81 Sample Output446113.34 View Code

?

POJ No.3484?Showstopper

DescriptionData-mining huge data sets can be a painful and long lasting process if we are not aware of tiny patterns existing within those data sets.One reputable company has recently discovered a tiny bug in their hardware video processing solution and they are trying to create software workaround. To achieve maximum performance they use their chips in pairs and all data objects in memory should have even number of references. Under certain circumstances this rule became violated and exactly one data object is referred by odd number of references. They are ready to launch product and this is the only showstopper they have. They need YOU to help them resolve this critical issue in most efficient way.Can you help them?InputInput file consists from multiple data sets separated by one or more empty lines.Each data set represents a sequence of 32-bit (positive) integers (references) which are stored in compressed way.Each line of input set consists from three single space separated 32-bit (positive) integers X Y Z and they represent following sequence of references: X, X+Z, X+2*Z, X+3*Z, …, X+K*Z, …(while (X+K*Z)<=Y).Your task is to data-mine input data and for each set determine weather data were corrupted, which reference is occurring odd number of times, and count that reference.OutputFor each input data set you should print to standard output new line of text with either “no corruption” (low case) or two integers separated by single space (first one is reference that occurs odd number of times and second one is count of that reference).Sample Input1 10 1 2 10 11 10 1 1 10 11 10 1 4 4 1 1 5 1 6 10 1 Sample Output1 1 no corruption 4 3 View Code

?

轉載于:https://www.cnblogs.com/Atanisi/p/8684339.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【算法总结】二分搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。