二分的经典问题 最大化最小值和最小化最大值

有点长~可以选自己想看的部分看~不过建议把刚开始的介绍看完~

不多说，先来一个在升序无重复元素的数组中二分搜索的板子。(l+r)/2=mid可能会爆int这种细节问题我们就放一边。

int a[MAX];int Binary_Search(int v)
{int l=0,r=n-1;while(l<=r){int mid=(l+r)/2;if(a[mid]==v)return mid;else if(a[mid]>v)r=mid-1;elsel=mid+1;}return l;
}

无重复元素的二分相信大家都会写，就不再赘述了。

下面给一个在非降序有重复元素的数组的二分搜索的板子。

int a[MAX];int Binary_Search(int v)
{int l=0,r=n-1;while(l<=r){int mid=(l+r)/2;if(a[mid]>=v)r=mid-1;elsel=mid+1;}return l;
}

为什么这么写没有问题呢，我们来考虑一下：(1)如果a[mid]>v的时候，令r=mid-1，这时候这样降低上限肯定是没有问题的。(2)如果a[mid]==v的时候，令r=mid-1，这时候会不会有问题呢，我们来仔细分析一下。如果a[mid]==v且这是唯一一个或者说第一个等于v的元素，我们把上限划为mid-1，那么后续的所有操作舍弃掉的必定是左边的区间，二分的最后一步是l==r的情况，这时候a[l]=a[r]=a[mid-1]只有当mid不合理时，我们才修改下限。这与最小化最大值问题有异曲同工之妙。当judge(mid)不合理时，我们才修改下限。

最小化最大值问题：(在满足题意的情况下求最小值)

CSU 1976

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=1976

Description

作为老人的小明非常忧伤，因为他马上要被流放到本部去了，住进全左家垅最有历史感的11舍真是一件非常荣幸的事情。
搬行李是个体力活，小明发现自己的行李太多啦，所以他决定去买很多个袋子来装走。到了超市的小明发现，不同大小的袋子居然价格一样？？？虽然买最大的自然最赚，但是小明是名远近闻名的环保人士，他觉得袋子只要能装下他的行李就够了，并且为了不麻烦收银的小姐姐(⊙o⊙)…，他也只会购买同一种大小的袋子。因此他希望在能装下所有行李的前提下，袋子越小越好。同时为了避免弄乱行李，小明希望同一个袋子装的是位置连续相邻的行李。
小明摸了摸口袋发现自己带的钱最多能买N个袋子，数学特别差的他不知道到底该买多大的才合适，所以想靠你来解决这个问题了。

Input

第一行为一个数字T（T<=10）表示数据组数
第二行为两个数字N（N <= 10^5）和 M（M <= 10^5）表示袋子个数和小明的行李个数
第三行为M个数字，第i个数字a[i]表示小明的第i个行李体积为a[i]（0

Output

输出一行表示袋子的最小体积（整数）

Sample Input

1
3 3
1 1 1

Sample Output

1

Hint

袋子不能装下体积大于其容积的物品
多个物品满足体积之和小于等于一个袋子的容积，就能被装进

题意就不说了吧，直接开始分析：最小容积是在m==n的时候取到的，这时候袋子的最小体积=物品的最大体积，最大容积是在只有一个袋子的时候取到的，这时候袋子的最小体积=物品的体积之和。我们取mid值，看在这种情况下，用掉的袋子的数量是否大于n，因为大于n的时候，这个mid值是必定不满足题意的，因此我们可以放心的令l=mid+1，反之我们令r=mid-1。

#include
#include
#include
#include
#include
#include
#define EPS 1e-12
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;int a[305];int main()
{int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);int MAX=0;int sum=0;for(int i=0;iMAX)MAX=a[i];}int l=MAX,r=sum;while(l<=r){int mid=(l+r)/2;int cnt=1;sum=0;for(int i=0;imid){sum=a[i];cnt++;}}if(cnt<=m)r=mid-1;elsel=mid+1;}printf("%d\n",l);}return 0;
}

POJ 3104

http://poj.org/problem?id=3104

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

Input

The 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).

Output

Output a single integer — the minimal possible number of minutes required to dry all clothes.

Sample Input

sample input #1
3
2 3 9
5sample input #2
3
2 3 6
5

Sample Output

sample output #1
3sample output #2
2

题目大意：有一堆衣服和一个散热片，给出每个衣服的潮湿程度，散热片一次只能给烘一件衣服，这衣服每分钟潮湿度减少k，其他的在空气中的衣服每分钟潮湿度减少1，问你使所有衣服全部晾干的最短时间是多少。

思路：最短时间是1，对潮湿程度进行排序，最长时间是a[n-1]。二分判断在当前mid值下，烘干所有衣服所花费的时间是否大于mid，若大于mid，必定不满足题意，我们可以令l=mid+1，否则令r=mid-1。我们用cnt表示烘干衣服所花费的时间，遍历数组，如果a[i]<=mid，那么就没必要用散热片烘干了，反之，我们假设这件衣服需要t次才能烘干，那么必定有t*k+mid-t>=a[i]，化简可以得到：t>=(a[i]-mid)/(k-1)；用函数ceil(x)可以得到大于等于x的最小整数。(x是double型）

#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;int a[100005];int main()
{int n,k;while(~scanf("%d",&n)){for(int i=0;imid)//不需要放到散热片上cnt+=ceil((a[i]-mid)*1.0/(k-1));if(cnt>mid)break;}if(cnt<=mid)r=mid-1;elsel=mid+1;}printf("%d\n",l);}return 0;
}

最大化最小值问题：(在满足题意的情况下求最大值)

POJ 2456

http://poj.org/problem?id=2456

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?

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 Input

5 3
1
2
8
4
9

Sample Output

3

Hint

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.

题目大意：大概就是把c头羊放到n个椅子上(英语不好ORZ)，求羊与羊之间间隔的最大值。

思路：读入n个椅子的位置并进行排序，下限就是a[i]-a[i-1]的最小值，上限就是两头羊的时候，a[n-1]-a[0]，然后二分，看在当前mid值的情况下，能放入多少个羊，如果可以放入的羊的个数小于n，此时的mid值必定不满足题意，我们修改r=mid-1，(注意！这里是修改r而不是修改l，因为要找最大值，所以我们在不满足题意的情况下才修改上限)；反之我们令l=mid+1。当然最后打印的值也要更改为r。

#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;int a[100005];int main()
{int n,c;scanf("%d %d",&n,&c);for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！