vlambda博客
学习文章列表

贪心算法简介

      贪心算法是从某一个初始状态出发，每次通过选取局部最优解向目标前进，并最终期望取得整体最优解的一种算法。由这个定义可知，贪心选择标准就是选择“当前最好”的决策，贪心算法根据这个标准进行决策，将原问题变成一个相似但规模更小的子问题，而后每一步选出来的一定是原问题整体最优解的一部分。

      如果一个问题贪心后只剩下一个子问题且有最优子结构，那么该问题就可以使用贪心算法。当一个问题的整体最优解包含其子问题的最优解时，我们称次问题具有最优子结构性质。

解题一般步骤

1、      设计数据找规律；

2、      进行贪心猜想；

3、      正确性证明（包括列举反例和严格的             数学证明）；

4、      程序实现。

例题（洛谷P1080国王游戏）：

题目描述

      恰逢 H国国庆，国王邀请n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

      国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数n，表示大臣的人数。

第二行包含两个整数 a和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 n行，每行包含两个整数a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

输入输出样例

说明/提示

【输入输出样例说明】

按1、2、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为2；

按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按2、3、1这样排列队伍，获得奖赏最多的大臣所获得金币数为9；

按 3、1、2这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；

按3、2、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为9。

因此，奖赏最多的大臣最少获得 2个金币，答案输出 2。

【数据范围】

对于 20%的数据，有 1≤ n≤ 10,0 < a,b < 8；

对于 40%的数据，有1≤ n≤20,0 < a,b < 8；

对于 60%的数据，有 1≤ n≤100；

对于 60%的数据，保证答案不超过 10^9；

对于 100%的数据，有 1 ≤ n ≤1,000,0 < a,b < 10000。

解题思路

      不妨先讨论相邻的二元组。由题意可知，相邻两个大臣交换位置不会对前面和后面的其他人的金币数造成影响。也就是说相邻两人位置交换只会对这两个人产生影响我们以此为切入点，分析调换相邻的两个人对答案的影响。

      设这两个人位置分别为i和i+1，左手数字为a[i]和a[i+1]，右手数字为b[i]和b[i+1]，两人的金币数为w[i]和w[i+1]。记  P[i]=a[1]*a[2]*a[3]*...*a[i]。

    未调换顺序时，k1=w[i]=P[i-1]/b[i]; k2=w[i+1]=P[i-1]*a[i]/b[i+1];则

ans1=max(k1,k2)

     调换顺序后k3=P[i-1]/b[i+1]; k4=P[i-1]*a[i+1]/b[i]; 则ans2=max(k3,k4)

     显然有k1<k4,k3<k2;如果ans1<ans2,那么必有k2<k4。化简可得a[i]*b[i]<a[i+1]*b[i+1];

      所以，为了ans取到最小值，我们需要将a[i]*b[i]较小的放在前面那么我们以a[i]*b[i]为关键字排序即可。同时，统计答案时一定不要忘了写高精度。

·END·

文案：张天泽

排版：郭泓业