第十一周测验（二分法）

迈不过友情╰ 2022-05-14 03:45 396阅读 0赞

8208 矩形分割 http://noi.openjudge.cn/ch0111/03/  
8211 派 http://noi.openjudge.cn/ch0111/05/  
8209 月度开销 http://noi.openjudge.cn/ch0111/06/  
8210 河中跳房子 http://noi.openjudge.cn/ch0111/10/  
1458 Aggressive cows http://bailian.openjudge.cn/practice/2456/

## 03:矩形分割 ##

描述

平面上有一个大矩形，其左下角坐标（0，0），右上角坐标（R,R)。大矩形内部包含一些小矩形，小矩形都平行于坐标轴且互不重叠。所有矩形的顶点都是**整点**。要求画一根平行于y轴的直线x=k（**k是整数**) ，使得这些**小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小**。并且，要使得大矩形在**直线左边的的面积尽可能大**。注意：若**直线穿过**一个小矩形，将会把它切成两个部分，分属左右两侧。

输入

第一行是整数R，表示大矩形的右上角坐标是(R,R) (1 <= R <= 1,000,000)。  
接下来的一行是整数N,表示一共有N个小矩形(0 < N <= 10000)。  
再接下来有N 行。每行有4个整数，L,T, W 和 H, 表示有一个小矩形的左上角坐标是(L,T),宽度是W，高度是H (0<=L,T <= R, 0 < W,H <= R). 小矩形不会有位于大矩形之外的部分。

输出

输出整数n，表示答案应该是直线 x=n。 如果必要的话，x=R也可以是答案。

样例输入

1000
    2
    1 1 2 1
    5 1 2 1

样例输出

> 【思路】这个题主要要注意两个要点：
> 
> 1. 小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小。
> 
> 可以采用二分法查找适合x=n的值，使得面积之差最小。如果左边的面积>右边的面积，说明面积之差还有可能会很小，继续right = mid -1，如果左边的面积<右边的面积，说明x=n的值还要往右移动，使得左边的面积更大一些，此时left = mid + 1.直到当x=n时，面积之差最小。
> 
> 2. 要使得大矩形在直线左边的的面积尽可能大。
> 
> 采用二分法，在满足第一个条件的基础上，查找适合的x=n的值，使得大矩形在左边的面积最大。如果面积之差不变，此时x的值还要往右移动，使得满足面积尽可能大，left = mid +1。如果面积之差改变，此时说明左边的面积大于了右边的面积，x=n的值太靠右了，需要right = mid - 1，往左移动一点。

![70][]

#include<iostream>
    using namespace std;
    struct node{
    	long long l,t,w,h;
    }; 
    node a[10010];
    int r,n;
    long long tot = 0;
    int ans;
    long long cha;
    
    int main()
    {
    	cin >> r >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		cin >> a[i].l >> a[i].t >> a[i].w >> a[i].h;
    		tot += a[i].w * a[i].h;//总面积 
    	}
    	int l, r1, m, l1 = r;
    	l = 0;
    	r1 = r;
    	cha = tot;
    	while(l <= r1)
    	{
    		m = (l + r1)/2;
    		long long ls = 0, rs;
    		for(int i = 1; i <= n; ++i)
    		{
    			if(a[i].l + a[i].w <= m) ls += a[i].w * a[i].h;//直线不穿过小矩形 
    			else if(a[i].l <= m) ls += (m - a[i].l) *a[i].h;//直线穿过小矩形 
    		}
    		rs = tot - ls;
    		if(ls >= rs)
    		{
    			cha = ls - rs;//面积差值最小 
    			l1 = m;
    			r1 = m-1;
    		}
    		else l = m + 1;
    	} 
    	l = l1;
    	r1 = r;
    	ans = l1;
    	while(l <= r1)//左边的面积最大 
    	{
    		m = (l + r1)/2;
    		long long ls = 0, rs;
    		for(int i = 1; i <= n ; ++i)
    		{
    			if(a[i].l + a[i].w <= m) ls += a[i].w * a[i].h;
    			else if(a[i].l <= m) ls += (m - a[i].l*a[i].h);
    		}
    		rs = tot - ls;
    		if(ls - rs == cha)//左边的大矩形面积最大 
    		{
    			ans = m; 
    			l = m + 1;
    		}
    		else r1 = m - 1;
    	}
    	cout << ans;
    	return 0;
    }

这个代码参考的别人的代码，只有9分，嗯嗯~，暂时卡住了没解决，还有一组数据没通过，后面再来更新~

## 05:派 ##

描述

我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。  
  
请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。

输入

第一行包含两个正整数N和F，1 ≤ N, F ≤ 10 000，表示派的数量和朋友的数量。  
第二行包含N个1到10000之间的整数，表示每个派的半径。

输出

输出每个人能得到的最大的派的体积，精确到小数点后三位。

样例输入

3 3
    4 3 3

样例输出

25.133

> 【思路】本题要注意几个地方：
> 
> 1. 精度问题，PI要至少精确到3.14159265
> 
> 2. 枚举的是体积，体积并不是整数，所以left = mid + 0.00001而不是left = mid + 1；
> 
> 3. 判断在mid（假设最大的派）的体积下，是否满足蛋糕够分的情况，即蛋糕分的块数count >= f+1,一定要记得加上主人自己。count >= f +1说明蛋糕还可以再分的大一些，因此蛋糕的体积用二分法枚举时，left = mid + 0.00001.

> 本题一定要注意精度！精度！精度！这是个坑！

#include<iostream>
    #include<iomanip>
    #define k 10010
    #define PI 3.1415926535897932
    double a[k];//存放每块蛋糕的体积 
    using namespace std;
    int n,f,d;
    bool find(double mid)
    {
    	int count = 0;
    	for(int i = 1; i <= n; ++i)
    	{
    		count += a[i]/mid;//a[i]/mid为第i块蛋糕可以被分为几份 
    	}
    	if(count >= f+1)//看蛋糕是否够分 
    		return true;
    	else 
    		return false;
    }
    int main()
    {
    	double maxa = 0, ans = 0;
    	cin >> n >> f;
    	for(int i = 1; i <= n; ++i)
    	{
    		cin >> d;
    		a[i] = PI*d*d;
    		if(maxa <= a[i]) maxa = a[i];
    	}
    	double l = 0, r = maxa;
    	while(l < r)//二分法查找合适的体积，要枚举体积，而不是半径 
    	{
    		double mid = (l+r)/2;
    		if(find(mid))
    		{
    			ans = mid;
    			l = mid + 0.00001;//必须至少5位小数，否则会报错 
    		} 
    		else r = mid - 0.00001;
    	}
    	cout << fixed << setprecision(3) << ans << endl;
    	return 0;
    }

## 06:月度开销 ##

描述

农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 *N* (1 ≤ *N* ≤ 100,000) 天里每天需要的开销。

约翰打算为连续的*M* (1 ≤ *M* ≤ *N*) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。

约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。

输入

第一行包含两个整数N,M，用单个空格隔开。  
接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。

输出

一个整数，即最大月度开销的最小值。

样例输入

7 5
    100
    400
    300
    100
    500
    101
    400

样例输出

500

提示

若约翰将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大月度开销为500。其他任何分配方案都会比这个值更大。

> 【思路】
> 
> 用二分法枚举每一种可能的开销最多月的最小开销。此时l为开销的最大值（fajo月开销至少要大于每一个月的钱）和r开销的总和（如果是开销的总和，就说明fajo月就是全部的月份），判断是否满足m个月即可。

#include<iostream>
    #define MAXN 100010
    using namespace std;
    int a[MAXN];
    
    bool judge(int mid, int a[], int n, int m)//判断是否能够在>=m个fajo月内，使得这些fajo月都满足不超过最大开销mid 
    {
    	int count = 0, sum = 0;
    	for(int i = 1; i <= n; ++i)
    	{
    		if(sum + a[i] > mid)//mid为最大的月度开销 
    		{
    			sum = a[i];//a[i]归到下个月进行计算 
    			++count;//多了一个月的开销被安排好了 
    		}
    		else sum += a[i];
    	}
        if(count >= m) 
        	return true;
    	else 
    		return false;
    }
    
    int main()
    {
    	int n, m, maxn = 0, tot = 0, mid = 0;
    	cin >> n >> m;
    	for(int i = 1; i <= n; ++i)
    	{
    		cin >> a[i];
    		if(maxn <= a[i]) maxn = a[i];
    		tot += a[i];
    	}
    	int l = maxn;
    	int r = tot;
    	while(l <= r)
    	{
    		mid = (l + r) / 2;
    		if(judge(mid,a,n,m)) 
    		{
    			l = mid + 1;
    		//	int ans = mid;
    			//cout << ans << endl;
    		}
    		else
    			r = mid - 1;
    		//cout << mid << " " << l <<" " << r << endl;		 
    	}
    	cout << mid << endl;
    	return 0;
    }

### 10:河中跳房子 ###

描述

每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ *L*≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有*N* (0 ≤ *N* ≤ 50,000) 个岩石，每个岩石与起点的距离分别为*Di (0 < Di < L)。*

在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。

农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多*M* (0 ≤ *M* ≤ *N*) 个岩石。

请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？

输入

第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。  
接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。

输出

一个整数，最长可能的最短跳跃距离。

样例输入

25 5 2
    2
    11
    14
    17
    21

样例输出

提示

在移除位于2和14的两个岩石之后，最短跳跃距离为4（从17到21或从21到25）

> 带符号32位int类型整数为-2147483648~2147483647[https://blog.csdn.net/y12345678904/article/details/52854230][https_blog.csdn.net_y12345678904_article_details_52854230]

>     关键思路就是：用两分法去推求最长可能的最短跳跃距离。
>     最初，待求结果的可能范围是[0，L]的全程区间，因此暂定取其半程(L/2)，作为当前的最短跳跃距离，以这个标准进行岩石的筛选。
>     筛选过程是：
>     先以起点为基点，如果从基点到第1块岩石的距离小于这个最短跳跃距离，则移除第1块岩石，再看接下来那块岩石（原序号是第2块），如果还够不上最小跳跃距离，就继续移除。。。直至找到一块距离基点超过最小跳跃距离的岩石，保留这块岩石，并将它作为新的基点，再重复前面过程，逐一考察和移除在它之后的那些距离不足的岩石，直至找到下一个基点予以保留。。。
>     当这个筛选过程最终结束时，那些幸存下来的基点，彼此之间的距离肯定是大于当前设定的最短跳跃距离的。
>     这个时候要看一下被移除岩石的总数，
>     如果总数>M，则说明被移除的岩石数量太多了（已超过上限值），进而说明当前设定的最小跳跃距离(即L/2)是过大的，其真实值应该是在[0, L/2]之间，故暂定这个区间的中值(L/4)作为接下来的最短跳跃距离，并以其为标准重新开始一次岩石筛选过程。。。
>     如果总数≤M，则说明被移除的岩石数量并未超过上限值，进而说明当前设定的最小跳跃距离(即L/2)很可能过小，准确值应该是在[L/2, L]之间，故暂定这个区间的中值(3/4L)作为接下来的最短跳跃距离。。。

最大最短距离：

![70 1][]

![70 2][]

#include<iostream>
    #define MAXN 50010
    using namespace std;
    int a[MAXN];
    int l, n, m;
    
    bool find(int mid)
    {
    	int now = 0, num = 0;
    	for(int i = 1; i <= n + 1; ++ i)
    	{
    		if(a[i] - a[now] >= mid)
    		{
    			++ num;//满足条件的石头个数 
    			now = i;
    		}		
    	}
    	if(num >= n - m + 1)//移除的石头可能太少了，需要增大距离 
    		return 1;
    	else
    		return 0;
    } 
    
    int main()
    {
    	cin >> l >> n >> m;
    	for(int i = 1; i <= n; ++i)
    		cin >> a[i];
    	int le = 0, mid, ans;
    	a[n+1] = l;
    	int ri = a[n+1];
    	while(le <= ri)
    	{
    	    mid = (le + ri)/2;//mid为最长可能的最短跳跃距离 
    		//cout << mid << " " << le << " " << ri << endl;
    		if(find(mid))
    		{
    			ans = mid;
    			le = mid + 1;
    		}
    		else
    			ri = mid - 1;		
    	}
    	cout << ans << endl;
    	//cout << mid << endl;
    	return 0;	 
    }

### 2456:Aggressive cows ###

描述

Farmer 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?

输入

\* Line 1: Two space-separated integers: N and C  
  
\* Lines 2..N+1: Line i+1 contains an integer stall location, xi

输出

\* Line 1: One integer: the largest minimum distance

样例输入

5 3
    1
    2
    8
    4
    9

样例输出

提示

OUTPUT 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.

来源

USACO 2005 February Gold

思路来源：[https://www.cnblogs.com/WangMeow/p/7535958.html][https_www.cnblogs.com_WangMeow_p_7535958.html]

> **解题新知：**
> 
>  **①题意：**农夫有N件牛舍，牛舍排在一条线上，第i号牛舍在xi的位置。但是他的小牛都很疯狂，彼此之间都会互相攻击。农夫为了防止牛之间互相伤害，决定要把每头牛都放在离其他牛尽可能远的牛舍。题目会给你牛舍的位置，牛的数量为2<=C<=N，也就是说如果C==N，那么牛舍就直接上来就放满了。
> 
> 用一组数据举例：
> 
> 5 5
> 
> 1
> 
> 3
> 
> 8
> 
> 4
> 
> 9
> 
> 最终输出结果应该为1，为什么呢，因为两头最近的牛不相互攻击的最大距离就是在 3位置和4位置的两头牛，即dmin=1。那么我们知道了其实就是要求**最大化最近的两头牛之间的距离！**
> 
> **②思路：**根据题意，要求最小值最大，我们可以利用二分和贪心结合的思想（类似POJ1064），我们可以猜最近两头奶牛间距离的最大值，每猜一个距离，进行判断，如果答案可行，则猜的距离可以再大些，如果答案不可行，则猜的距离就要再小些。在判断答案是否可行时，可以用cnt来记录匹配到槽的奶牛数，先将第一头奶牛放在第一个槽，然后依次枚举每个槽，当枚举的槽与前一个放奶牛的槽的距离大于等于猜的答案时，cnt加1，最后判断cnt是否大于等于奶牛数即可。

#include<iostream>
    #include<algorithm>
    #define MAXN 100010
    using namespace std;
    int n,m;
    int a[MAXN];
    bool find(int mid)
    {
    	int t = 1,num = 1;
    	for(int i = 2; i <= n; ++i)
    	{
    		if(a[i] - a[t] >= mid)//mid是最小最大距离，任何两个数的距离之差肯定是大于等于mid 
    		{
    			++ num;//将牛放进去 
    			t = i;
    		}
    	}
    	if(num >= m) //距离可能过小，需要继续更新最小最大距离 
    		return true;
    	else 
    		return false;
    }
    int main()
    {
    	cin >> n >> m;
    	for(int i = 1; i <= n; ++i)
    		cin >> a[i];
    	sort(a+1,a+1+n);
    	int l = 0, ans = 0;
    	int r = a[n] - a[1];
    	while(l <= r)
    	{
    		int mid = (l+r)/2;
    		if(find(mid))//最小最大距离 
    		{
    			ans = mid;
    			l = mid + 1;
    		}
    		else
    			r = mid - 1;
    		
    	}
    	cout << ans << endl;
    	return 0;
    }

二分法题解：[https://www.cnblogs.com/hyl2000/p/5734908.html][https_www.cnblogs.com_hyl2000_p_5734908.html]

这类问题有个明显的特征：使最小值最大或者使最大值最小。这个时候大概步骤就是先对读进来的数据进行排序（因为二分查找是在有序的数据上进行的）然后执行二分。其中二分里的check函数是最关键的部分，例如第一题中我们就是二分答案，然后在check中贪心的来安排牛的位置，看是否能够满足答案。而第二题也是二分答案，check中按我们求出的答案把不满足答案的石头撤掉，看是否能够满足答案。这就是check的大概思路：即检查是否能够满足答案。

二分中还有一个重要的细节：求最大值的最小值时mid=(l+r)/2，l=mid+1，r=mid；而查找最小值的最大值时mid=(l+r+1）/2，l=mid，r=mid-1。不然程序会陷入死循环，或者得不到正确答案。

最后一点就是实数二分的时候因为精度需要常常我们会让程序一直进行计算，然而由于计算时的精度误差，常常也会使程序效率低下或者死循环。一般来讲我们这时可以限制二分次数，一般60-70次即可满足精度需要，这样可以提高程序效率，避免TLE的情况出现。

最最后一点，这类问题数据量一般都非常大，记得用scanf读入，第一题我就因为用cin而TLE了，改成scanf之后马上就过了。。。。。

二分法求最大最小值模板：

#include<iostream>
    using namespace std;
    bool judge(int mid)//判断是否符合条件
    {
    	for(循环)
    	{
    		求解计数结果num，++num; 
    	} 
    	if(num与题目边界条件)
    		return true;
    	else
    		return false; 
    } 
    int main()
    {
    	int l, r, ans = 0;
    	l = ;//l和r的具体值要看题目是需要枚举的什么 
    	r = ;
    	while(l <= r)
    	{
    		int mid = (l+r)/2;//mid = l + (r-l)/2
    		if(judge(mid))
    		{
    			ans = mid;
    			l = mid + 1;//也有可能不是1，可能是一个小数，要看具体的间距 
    		}
    		else
    		 	r = mid -1;
    	 } 
    	 cout << ans << endl;
    	 return 0; 
    }

[70]: /images/20220514/9ba252d3964547fab7b84741f5d6626d.png
[https_blog.csdn.net_y12345678904_article_details_52854230]: https://blog.csdn.net/y12345678904/article/details/52854230
[70 1]: /images/20220514/a22e04adc325491d92357ac488c27a33.png
[70 2]: /images/20220514/71a8604effdd43dcb61e57bdc8c6298e.png
[https_www.cnblogs.com_WangMeow_p_7535958.html]: https://www.cnblogs.com/WangMeow/p/7535958.html
[https_www.cnblogs.com_hyl2000_p_5734908.html]: https://www.cnblogs.com/hyl2000/p/5734908.html