二分搜尋，POJ2456，NYOJ 914， 區間移位-藍橋杯-曆屆試題

二分搜尋是不斷縮減可能解的範圍來得到最優解， 因為每次是折半， 是以指數爆炸有多快，這個效率就有多高

1. POJ2456為例， 傳送門

   

   簡而言之， 就是将牛之間的距離的最小值最大化。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n, m;
int num[100005];

bool can(int mid)
{
	int sum = 1, last = 0;
	for(int i = 1; i < n; i++)
	{
		if(num[i] - num[last] >= mid)
		{
			sum++;
			last = i;
		}
	}

	return sum >= m;
}

int main()
{
	scanf("%d %d", &n, &m);
	int maxl = -1;
	for(int i = 0; i < n; i++)
		scanf("%d", &num[i]), maxl = max(maxl, num[i]);

	sort(num, num + n);
	int l = 1, r = maxl, mid, ans;

	while(l <= r)		//最優解隻有一個， 通過二分不斷縮小解可能 額日志的範圍， ans儲存結果。
	{
		mid = (l + r) >> 1;
		if(can(mid))
			ans = mid, l = mid + 1;
		else
			r = mid - 1;
	}

	printf("%d", ans);
}
           

1. 最大化平均值 ， NYOJ 914

最先想到的就是用v i/ wi進行貪心求解， 但用上面的例子， 可知所選物品是0号和1号

錯誤的原因是vi / wi對總體v / w的結果的影響是跟wi成正比的， 跟選0号和1号相比， o号的影響更大導緻總體更大。

二分解決這種問題的難點在于選什麼進行二分搜尋， 這裡我們選擇X( k個物品的機關重量的價值）， 判斷條件為

通過化簡有

NYOJ 914通過代碼

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<functional>
using namespace std;

int n, k;
int w[10004], v[10004];
double temp[10004];

bool can(double mid)
{
	for(int i =0; i < n; i++)
		temp[i] = v[i] - mid * w[i];
	sort(temp, temp + n, greater<double>());			//greater<double>(),實作由大到小排序

	double re = 0;
	for(int i = 0; i < k; i++)
		re += temp[i];

	return re >= 0;
}

int main()
{

	while(~scanf("%d %d", &n, &k))
	{
		double maxl = -1;
		for(int i = 0; i < n; i++)
			scanf("%d %d", &w[i], &v[i]), maxl = max(maxl, v[i] * 1.0 / w[i]);

		double l = 0, r = maxl, mid;
		for(int i = 0; i < 100; i++)
		{
			mid = (l + r) / 2;
			if(can(mid))
				l = mid;
			else
				r = mid;
		}
		
		printf("%.2lf\n", l);
	}

}
           

1. 藍橋杯-曆屆試題 區間移位， 傳送門

   問題描述

   　　數軸上有n個閉區間D1,…,Dn。其中區間Di用一對整數[ai, bi]來描述，滿足ai < bi。已知這些區間的長度之和至少有10000。是以，通過适當的移動這些區間，你總可以使得他們的“并”覆寫[0, 10000]——也就是說[0, 10000]這個區間内的每一個點都落于至少一個區間内。

   　　你希望找一個移動方法，使得位移差最大的那個區間的位移量最小。

   　　具體來說，假設你将Di移動到[ai+ci, bi+ci]這個位置。你希望使得maxi |ci|　　最小。

   輸入格式

   　　輸入的第一行包含一個整數n，表示區間的數量。

   　　接下來有n行，每行2個整數ai,　　bi，以一個空格分開，表示區間[ai, bi]。保證區間的長度之和至少是10000。

   輸出格式

   　　輸出一個數，表示答案。如果答案是整數，隻輸出整數部分。如果答案不是整數，輸出時四舍五入保留一位小數。

   樣例輸入

   2

   10 5010

   4980 9980

   樣例輸出

   20

   樣例說明

   　　第一個區間往左移動10；第二個區間往右移動20。

   樣例輸入

   4

   0 4000

   3000 5000

   5001 8000

   7000 10000

   樣例輸出

   0.5

樣例說明

　　第2個區間往右移0.5；第3個區間往左移0.5即可。

　　

資料規模和約定

　　對于30%的評測用例，1 ≤ n ≤ 10；

　　對于100%的評測用例，1 ≤ n ≤ 10000，0 ≤ ai < bi　　≤ 10000。

類似的二分方法， 但10個測試用例隻過了8個得了80分，不是vip看不到無法通過的樣例，就這樣吧， 下面是80分的代碼

#include<iostream>
#include<set>
#include<cstdio>
using namespace std;

typedef pair<int, int> p;
multiset<p> ms;
int N = 20000;

bool can(int num)
{
	int now = 0;
	multiset<p> ::iterator it;
	int tl, tr;
	for(it = ms.begin(); it != ms.end(); it++)
	{
		p t = *it;
		tl = t.first;
		tr = t.second;
		if(tl - num <= now && tr + num >= now)
		{
			if(tl + num <= now) now = tr + num;
			else now += tr - tl;
		}
		
		if(now >= N) return true;
	}
	
	return now >= N;
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		ms.insert(p(a * 2, b * 2));
	} 
	
	int now = 0;
	int l = 0, r = N, mid;
	while(l < r)
	{
		mid = (l + r) >> 1;
		if(can(mid))
		r = mid;
		else
		l = mid + 1;
	}
	
	double re = l * 1.0 / 2;
	cout << re << endl;
	return 0; 
}