朴素的贪心法(中)构造法
构造法没有明显决策过程，只是把决策放到了推导阶段，灵活性高，大多数刚接触贪心算法的人不知道如何下手
例1:数字拆分 
思路1:拆成尽可能多的2，因为当a,b>2时，a x b > a + b
问题:需要拆成“不同的”数字，2只能出现一次
思路2:拆成尽可能小的数字，比如9 = 2 + 3 + 4，就好过9 = 5 + 4，因为2 x 3 > 2 + 3
问题:10=2+3+4+...1? 余1怎么办？
1补到4上变成5，10=2+3+5 是最优拆分
why?
如果把10改为12呢 ?
12=2+3+4+...3
把3都分配给4，变成2+3+7，2x3x7=42不是最优，
例:2+4+6，2x4x6=48
最优方案:最后三个数各加1，3x4x5=60
余数分配规律
越趋向平均越好，比如给2x4分配1，那么3x4>2x5
由于数字必须不同，不保证能从第一个数开始加。
例:2+3+4如果把1加给2，变成3+3+4，则两个3冲突。
除非——余数足够大，可以分给下一个数，下下一个数......直到最后一个数
数字拆分:解法
1.将N拆分成2+3+4+...+(M-1)+M+K(余数)的形式0≤K≤M
2.从M开始向前倒推K个数，给每个数字都加1，变成2+3+...+(M-K-1)+(M-K+1)+(M-K+2)+...+M+(M+1)。
特例:K=M时，最后一个数是M+2
3.可以证明该拆分为最优~ 
代码:数字拆分 
#include<bits/stdc++.h> using namespace std; const int MAX_RAND_TIME = 1000000; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; int a[n]; double avg = 0; for (int i = 0; i < n; i++) { cin >> a[i]; avg += a[i]; } avg /= m; double res = INT_MAX; for (int times = 0; times < MAX_RAND_TIME; times++) { random_shuffle(a, a + n); int sum[m]; memset(sum, 0, sizeof(sum)); for (int i = 0; i < n; i++) { int min_j = 0; for (int j = 1; j < m; j++) if (sum[j] < sum[min_j]) min_j = j; sum[min_j] += a[i]; } double s = 0; for (int i = 0; i < m; i++) s += (avg - sum[i]) * (avg - sum[i]); s = sqrt(s / m); res = min(res, s); } cout << fixed << setprecision(2) << res << endl; return 0; }
适用构造法的问题特征
1.通常有一个比较直观，容易想到或者计算出来的“规律“
2.边界条件经常需要特殊判断和处理
3.决策过程隐含在规律和边界条件中
例2:守望者的逃离(NOIP2007)
步骤1:寻找规律
- 直观感觉:闪现肯定快，但是消耗法术，如果法术不够需要原地休息，等法术恢复才能用
- 需要通过计算来比较速度(闪现 vs 走)
- 先看极端情况(一开始0能量)
- 以7秒为一个周期，只要剩余时间大于等于7秒，就使用休息+闪现来前进。7秒后能量值会恢复到起始值
- 每次只要法力攒够一次闪现就立刻闪，不够就原地休息恢复法力。如果某一次闪现后总移动距离大于S，则逃出生天
- 边界条件:如果剩余时间小于7秒呢?
步骤2:边界情况
剩1秒
- 不够恢复+闪现1次
- 直接走更快，移动距离17米
剩2秒
- 剩余能量>=6:足够恢复+闪现1次，移动距离60米
- 剩余能量<6:来不及恢复法力+闪现，直接走更快，移动距离17x2=34米
剩3秒:
最多只能恢复8点能量+闪1次
- 剩余能量>=2:恢复+闪现1次，移动60米
- 剩余能量<2:直接走更快，移动距离17x3=51米
剩4秒
- 假设一开始剩9点能量，恢复1秒闪1次后，能量剩余3需要恢复2秒再闪，来不及，所以最多只够闪1次
- 直接走移动距离17x4=68米，大于闪1次的60米，所以干脆直接走
剩5秒
- 剩余法术>=8时，足够恢复+闪2次，移动距离60x2=120米
- 否则，直接走，移动距离17x5=85米，那么如果闪1次需要走至少2秒，也就是60+17x2=94米，才会比直接走快，所以2<=剩余法术<8时，休息2秒，闪1次，走2秒最快不则直接走更快
剩6秒
- 剩余法术>=4时，足够恢复+闪2次，移动距离60x2=120米
- 否则，直接走，移动距离17x6=102米，那么如果闪1次需要走至少3秒，也就是60+17x3=111米，才会比直接走快，所以2<=剩余法术<4时，休息2秒，闪1次，走3秒最快不则直接走更快
代码：守望者的逃离
#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, s; cin >> n >> s; int p, y, min_p = INT_MAX - s; long long total = 0; for (int i = 0; i < n; i++) { cin >> p >> y; min_p += s; if (min_p > p) min_p = p; total += min_p * y; } cout << total << endl; return 0; }
构造法问题类别1:划分问题
- 要素1:有被划分的对象
- 数字拆分的N，守望者的逃离的总距离S
- 要素2:有阶段不定的划分方法
- 拆分成若干正整数 和，拆分成走路/闪现区间
- 要素3:有划分方案好坏的判定方法
- 乘积最大，总时间最短
- 1.起始状态和目标状态都是一系列元素的排列或者组合
- 目标状态是将起始状态的所有数字重新排列
- 2规定了一组状态转移的方法，也就是“变化”的方法
- 交换两个不同位置的数字
- 求的是从起始状态，通过一系列状态转移，变换到目标状态所需要的最小代价
- 最少的交换次数
三值交换:找规律
- 第一反应:先试试看怎么交换，可以让序列变成升序
- 统计1,2,3分别有多少个(记为count[1]/count[2]/count[3])这样就知道1,2,3排好序后分别都是第几位到第几位
- 1在排序后的范围是第1位到第count[1]位，在这个范围外的1都应该被交换进来
三值交换:最优交换 
代码:三值交换 
#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; int a[n + 1], count[4]; memset(count, 0, sizeof(count)); for (int i = 1; i <= n; i++) { cin >> a[i]; count[a[i]] ++; } int res = 0; int j2 = count[1] + 1, j3 = count[1] + count[2] + 1; for (int i = 1; i <= count[1]; i++) { if (a[i] == 2) { while (j2 <= count[1] + count[2] && a[j2] != 1) j2 ++; if (j2 <= count[1] + count[2]) { int tmp = a[i]; a[i] = a[j2]; a[j2] = tmp; res ++; } } else if (a[i] == 3) { while (j3 <= n && a[j3] != 1) j3 ++; if (j3 <= n) { int tmp = a[i]; a[i] = a[j3]; a[j3] = tmp; res ++; } } } int j = count[1] + 1; for (int i = 1; i <= count[1]; i++) { if (a[i] != 1) { while (j <= n && a[j] != 1) j ++; if (j <= n) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; res ++; } } } for (int i = count[1] + 1; i <= count[1] + count[2]; i++) if (a[i] == 3) res ++; cout << res << endl; return 0; }
状态转移问题:一般步骤
1.找出一种从起始状态转移到目标状态的方法，这个方法不一定是最优，但一定要是可行并且套路化的方法
2.挖掘出这个转移方法的额外步骤/代价
3.通过一定的规则，去掉这个额外的步骤和代价
希望对你有帮助！加油！
若您认为本文内容有益，请不吝赐予赞同并订阅，以便持续接收有价值的信息。衷心感谢您的关注和支持！
