上次我们讲了贪心, 上题:
题目描述:
RFdragon 摘了 n 种果子, 每种果子堆成一堆, 现在 RFdragon 打算将所有果子运回家, 因此决定将所有果子合并成一堆. 每次 RFdragon 可以选择任意两堆果子进行合并, 消耗等同于两堆果子质量之和的力气. 请你求出一个合并方案, 使得 RFdragon 消耗的力气最少.
输入描述:
第一行一个正整数 n.
第二行 n 个正整数, 表示每堆果子的质量.
输出描述:
一个正整数, 表示消耗力气的最小值.
输入样例:
5
3 2 5 2 1
输出样例:
29
其他说明:
n<100000, 所有数据均在 int 范围内.
今天我们要讲的是二分. 设想这样一个场景: 让你从 1~100 之间猜一个数, 每次告诉你大了或者小了, 要求尝试次数最少, 你会猜几? 想都不用想, 肯定先猜 50. 这个时候, 你已经在用二分的思想来解决问题了. 二分主要分两种: 二分查找和二分答案. 我们先来看二分查找. 我们直接来看一道题:
题目描述:
输入 n 个数, 将 n 个数从小到大排序, 问 k 排在第几.
输入描述:
第一行两个正整数 n 和 k, 中间用一个空格隔开.
第二行有 n 个正整数, 中间有一个空格隔开.
输出描述:
一个正整数, 表示 k 排在第几位.
输入样例:
5 7
7 3 5 6 9
输出样例:
4
其他说明:
n<1000000, 所有输入数据均在 int 范围内, 保证没有重复的数.
它要怎么用二分来实现呢? 首先, 不用说, 肯定要将输入的所有书进行排序. 那之后呢? 我们还回到刚才猜数的例子. 假设你猜了 50, 告诉你 50 小了, 你就排除了 1~50 之间的所有数, 范围变为 51~100; 你再猜 75, 假如 75 也小了, 那你又排除了 51~75 之间的所有数, 范围变为 76~100. 因此, 我们需要两个数来记录数据的范围. 我一般喜欢用 head 和 tail 进行表示, 如下:
int head=1,tail=n;
head 表示最小值, tail 表示最大值. 为什么 tail 要等于 n 呢? 这是因为, n 是数组中最大的数的下标, 这个数再大, 下标也不可能超过 n. 每次取一个中间值, 表示我们 "猜" 的那个数.
- mid=(head+tail)/2;
- if(a[mid]>k)
- tail=mid-1;
- else if(a[mid]<k)
- head=mid+1;
- else
- {
- printf("%d",mid);
- return 0;
- }
这就是我们 "猜" 数并缩小范围的过程. 掌握了核心代码, 题就不难做了. 完整代码如下:
- #include<cstdio>
- int n,k,a[1000000],head=1,tail,mid;
- int main()
- {
- scanf("%d %d",&n,&k);
- tail=n;
- for(int i=1;i<=n;i++)
- scanf("%d",&a[i]);
- while(head<=tail)
- {
- mid=(head+tail)/2;
- if(a[mid]==k)
- {
- printf("%d",mid);
- return 0;
- }
- else if(a[mid]>k)
- tail=mid-1;
- else
- head=mid+1;
- }
- return 0;
- }
这就是二分查找. 那么二分答案又是什么呢? 有一些题中, 答案很难被直接确定, 需要先确定范围, 然后在范围中逐渐尝试. 用一般的查找方法自然很慢, 但用二分来查找答案就快的多了. 为了让大家更好理解二分答案, 先上一道题:
题目描述:
RFdragon 家里有一些废品, 由于废品实在太多了, 因此需要分批运走. 黑心的收废品的叔叔为了盈利, 不但不给钱, 反而还向 RFdragon 索要工钱. RFdragon 好心的同意了.
RFdragon 会将所有的废品分成 n 批运走, 运走每批废品都要花一定量的钱. 由于叔叔很黑心, 因此向 RFdragon 提出以下要求: RFdragon 每天给叔叔 k 元钱, k 是一个定值, 叔叔会运走几批废品, 但是这几批废品必须是连续的, 并且每次必须将一整批全部运走; 如果运走几批废品后钱有剩余, 但不够运走下一批废品, 那么剩下的钱会被叔叔收入腰包. 由于忍受不了废品散发的味道, RFdragon 要求运走所有废品的天数不能超过 m 天, 并且 k 越小越好. 请你帮他求出 k 的最小值.
输入描述:
第一行三个正整数, 中间用空格隔开, 分别表示 n,m.
第二行有 n 个正整数, 表示运走每批废品的价格.
输出描述:
一个正整数, 表示 k 的最小值.
其他说明:
所有数据 < 10000.
首先, 我们要确定二分范围. 最小值一定是所有废品中花钱最多的那个, 最大值一定是所有废品所花钱数之和. 问题来了, 我们每次确定一个 mid 值之后, 如何判断这个 mid 值是否可以满足题意呢? 我们不妨写一个 check 函数.
- bool check(int x)// 参数 x 表示假设 k=x
- {
- int cur=x,sum=1;//cur 表示当前剩余钱数, sum 表示运走所有废品所需天数
- for(int i=1;i<=n;i++)
- {
- if(cur>a[i])
- cur-=a[i];// 假设剩余钱数能运走当前这批废品, 就让叔叔运走他
- else
- {
- cur=x-a[i];
- sum++;// 否则就让叔叔 (使用) 明天 (的钱) 运走他
- }
- }
- return sum<=m;
- }
完整代码如下:
- #include<algorithm>
- #include<cstdio>
- using namespace std;
- int n,m,a[10000];
- bool check(int x)
- {
- int cur=x,sum=1;
- for(int i=1;i<=n;i++)
- {
- if(cur>a[i])
- cur-=a[i];
- else
- {
- cur=x-a[i];
- sum++;
- }
- }
- return sum<=m;
- }
- int main()
- {
- int head=0,tail=0,mid;
- scanf("%d %d",&n,&m);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- tail+=a[i];
- head=max(head,a[i]);
- }
- while(head<tail)
- {
- mid=(head+tail)/2;
- if(check(mid))
- tail=mid;
- else
- head=mid+1;
- }
- printf("%d",head);
- return 0;
- }
这就是二分的用法, 你学会了吗?
- // 答案代码
- #include<algorithm>
- #include<cstdio>
- using namespace std;
- int n,a[10000],ans;
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%d",&a[i]);
- sort(a+1,a+1+n);
- for(int i=1;i<=n;i++)
- {
- a[i]+=a[i-1];
- ans+=a[i];
- }
- printf("%d",ans);
- return 0;
- }
- Created by RFdragon
来源: http://www.bubuko.com/infodetail-3054305.html