二分与贪心算法（POJ4110圣诞老人的礼物，POJ 3104 烘晾衣服）

1.二分查找

前提是: 已经排序好的序列

在查找元素时, 首先与序列中间的元素进行比较

• 如果大于这个元素, 就在当前序列的后半部分继续查找

• 如果小于这个元素, 就在当前序列的前半部分继续查找

• 直到找到相同的元素, 或者所查找的序列范围为空为止

伪码描述

left = 0, right = n -1 while (left <= right)

mid = (left + right) / 2

case

x[mid] < t:left = mid + 1;

x[mid] = t:p = mid; break;

x[mid] > t:right = mid -1;

return -1;

注意：我们在更新left和更新right的时候，一定是加1和减1， 不要只是更新mid，否则的话呢，整个程序会处在一个死循环当中。

2.贪心算法

问题求解时, 总是做出在当前看来是最好的选择

• 即不保证全局最优,仅是在某种意义上的局部最优解

贪心算法设计的关键是贪心策略的选择

自顶向下计算

• 通过贪心选择, 将原问题规约为子问题

贪心的基本思想

1->建立数学模型来描述问题

2->把求解的问题分成若干个子问题

3->对每一子问题求解, 得到子问题的局部最优解

4->把子问题的解局部最优解合成原来解问题的一个解

例题1，POJ4110圣诞老人的礼物

• 圣诞节来临了, 在城市A中圣诞老人准备分发糖果,

现在有多箱不同的糖果

• 每箱糖果有自己的价值和重量

• 每箱糖果都可以拆分成任意散装组合带走

• 圣诞老人的驯鹿最多只能承受一定重量的糖果

• 请问圣诞老人最多能带走 多大价值的糖果

程序输入

• 第一行由两个部分组成, 分别为 • 糖果箱数正整数 n (1 <= n <= 100)

• 驯鹿能承受的最大重量正整数 w (0 < w < 10000) 两个数用空格隔开

• 其余n行每行对应一箱糖果, 由两部分组成 • 一箱糖果的价值正整数 v

• 一箱糖果的重量正整数 w 中间用空格隔开

程序输出

• 输出圣诞老人能带走的糖果的最大总价值, 保留1位小数

• 输出为一行, 以换行符结束

样例输入

4 15

100 4

412 8

266 7

591 2

样例输出

1193.0

解题思路

装尽可能多的糖果 贪心!!!

• 先放总重量大的糖果? 可是，重量大的不一定价值高

• 先放总价值高的糖果? 但是呢，总价值高的重量可能很大

• 如何贪心地选择最佳的糖果?如果可以选择 “单位价值最大”那就可以啦

由于每箱糖果可以任意组合，所以一定可以放入所有糖果，或者驯鹿能承受最大容量被放满

• 因此放入的总重量是确定的

只用选择放入单位重量价值高的糖果

• 将糖果按单位重量价值从高到低排序, 依次放入，直到放满或者放完为止

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 110


//每箱糖果
struct Box
{
int v, w; //价值和重量
double density; //单位重量的价值
};

int n, w;
Box boxes[MAXN];
double totw, totv;

//箱子按单位重量价值排序
bool operator < (const Box &a, const Box &b)
{
    return a.density < b.density;
}

int main()
{
    cin >> n >> w;
    for ( int i = 0; i < n; ++i )
    {
        cin >> boxes[i].v >> boxes[i].w;
        boxes[i].density = 1.0 * boxes[i].v / boxes[i].w ;//计算单位重量的价值
    }
        sort(boxes, boxes+n); //按单位重量的价值排序
        totw = totv = 0;
        for (int i = n - 1;i >= 0;--i) //按单位重量的价值从大到小依次放入
            if (totw + boxes[i].w <= w)
            { //未放满
                totw += boxes[i].w;
                totv += boxes[i].v;
            }
            else
            { //已放满
                totv += boxes[i].density * (w - totw); totw = w;
                break;
    }
      printf("%.1lf\n", totv);
         return 0;
}

           

例题2，POJ 3104 烘晾衣服

问题描述

现有 n 件衣服需要烘干，每件衣服的含水量为 ai

• 如果自然晾干, 每分钟含水量减少 1

• 如果使用烘干机烘干, 每分钟含水量减少 k (直至为0)

只有一台烘干机, 每次只能烘干一件衣服 且一次至少使用1分钟 求使所有衣服含水量为0的最少时间是多少

程序输入

• 输入包含三行

• 第一行是一个整数 n (1 ≤ n ≤ 100000),

表示衣服的数量

• 第二行有n个整数,

分别表示各件衣服的含水量 ai (1 <= ai <= 10^9)

• 第三行是一个整数 k (1 <= k <= 10^9),

表示烘干机1分钟减少的水量

程序输出

• 输出一行, 表示最少需要的时间

样例输入

3

23 9 5

样例输出

3

解题思路

要求最小的时间

问题转换:

最小值问题 -> 判定性问题

• 判断在时间X内,是否能晾干/烘干所有的衣服

这个问题满足单调性的条件对时间X进行二分来解决!对于给定的时间X, 依次判断每一件衣服 i

• 如果ai<=X,则该衣服可以自然烘干

• 否则说明需要烘干机,

因为多用 1分钟 烘干机, 可以多减少 (k-1) 的水量,至少需要 ceil((X – ai) / (k-1)) 分钟的烘干机

如果所有衣服需要烘干机的时间总和 <= X 则说明时间X是可行的, 否则说明不可行

重点函数分析 -> 判断X是否可行

bool check(X)

{

当前需要烘干机时间 = 0;

for ( 所有的衣服 )

{

if ( 第i件衣服含水量 > X )

{

当前总计需要烘干机时间 += 第i件衣服至少需要的烘干机时间;

}

}

//判断最后的烘干机时间是否小于等于X

return 当前需要烘干机时间 <=X

}

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAXN (100000+10)
int n; //n件衣服
int l, r, mid; //用于判定时间X,所考虑的左右及中值
int k; //烘干机1分钟减少的水量
int a[MAXN];

//判断时间为ans是否可行
bool check(int ans)
{
int now = 0; //需要烘干机的时间
for (int i = 0; i < n; ++i )
if (a[i] > ans)
{
    now += (a[i] - ans - 1) / (k - 1) + 1; //第i件衣服需要烘干机的时间,注意是(k-1)
        // [a/k] = (a-1)/k + 1
    if (now > ans)
        return false;
}
return true;
}
int main()
{
    cin >> n;
    l = 0; r = 0;
    for (int i = 0;i < n;++i)
    {
        cin >> a[i];
        if (a[i] > r) r = a[i];
        
    }
    cin >> k;
    if (k == 1)
        cout << r << endl; //k=1, 直接输出, 避免除0的情况
    else {
            //二分答案,判断可行性
        while (l <= r)
        {
        mid = (l + r) / 2;
        if (check(mid)) r = mid - 1;
        else l = mid + 1;
    }
        cout << l << endl;
}
return 0;
}