算法与数据结构高手养成:朴素的贪心法(中)构造法

简介: 算法与数据结构高手养成:朴素的贪心法(中)构造法

朴素的贪心法(中)构造法

构造法没有明显决策过程,只是把决策放到了推导阶段,灵活性高,大多数刚接触贪心算法的人不知道如何下手

例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.通过一定的规则,去掉这个额外的步骤和代价

希望对你有帮助!加油!

若您认为本文内容有益,请不吝赐予赞同并订阅,以便持续接收有价值的信息。衷心感谢您的关注和支持!

目录
相关文章
|
4月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
112 1
|
1月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
86 29
|
1月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
95 25
|
1月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
72 23
|
3月前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
84 20
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
|
4月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
4月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
102 1
|
4月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
64 1
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
158 77