算法学习系列(三十五):贪心(杂)

目录

  • 引言
  • 一、合并果子(Huffman树)
  • 二、排队打水(排序不等式)
  • 三、货仓选址(绝对值不等式)
  • 四、耍杂技的牛(推公式)

引言

上一篇文章也说过了这个贪心问题没有一个规范的套路和模板,主要还是因题而异,到了考场上基本是靠猜,所以本篇文章主要还是以讲题为主。


一、合并果子(Huffman树)

思路:这道题其实是道Huffman的问题,就是怎么让体力值最小,那么肯定是最开始从最小的合并,因为刚开始合并成一堆,又因为最后要合并成一堆,相当于以前的会再次移动一次,所以肯定前面合并的要移动的次数肯定是会比后面移动的次数多的,所以先把移动小的,当然要更优。

题目描述:

在一个果园里,达达已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。

达达决定把所有的果子合成一堆。

每一次合并,达达可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。

可以看出,所有的果子经过 n−1 次合并之后,就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使达达耗费的体
力最少,并输出这个最小的体力耗费值。

例如有 3 种果子,数目依次为 1,2,9。

可以先将 1、2 堆合并,新堆数目为 3,耗费体力为 3。

接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。

所以达达总共耗费体力=3+12=15。

可以证明 15 为最小的体力耗费值。

输入格式
输入包括两行,第一行是一个整数 n,表示果子的种类数。
第二行包含 n 个整数,用空格分隔,第 i 个整数 ai 是第 i 种果子的数目。

输出格式
输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。
输入数据保证这个值小于 231。

数据范围
1≤n≤10000,1≤ai≤20000
输入样例:
3 
1 2 9 
输出样例:
15

示例代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int n;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    priority_queue<int, vector<int>, greater<int>> heap;
    
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        int t;
        cin >> t;
        heap.push(t);
    }
    
    LL res = 0;
    while(heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        
        res += a + b;
        heap.push(a+b);
    }
    
    cout << res << endl;
    
    return 0;
}

二、排队打水(排序不等式)

思路:要让总的等待时间最短那么肯定是让时间最长的人靠后,短的靠前,排个序就行了。

题目描述:

有 n 个人排队到 1 个水龙头处打水,第 i 个人装满水桶所需的时间是 ti,请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?

输入格式
第一行包含整数 n。
第二行包含 n 个整数,其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。

输出格式
输出一个整数,表示最小的等待时间之和。

数据范围
1≤n≤105,1≤ti≤104
输入样例:
7
3 6 1 4 2 5 7
输出样例:
56

示例代码:

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int n;
int a[N];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    
    sort(a+1, a+n+1);
    
    LL res = 0;
    for(int i = 1; i <= n; ++i)
    {
        res += a[i] * (n - i);
    }
    
    cout << res << endl;
    
    return 0;
}

三、货仓选址(绝对值不等式)

思路:由下图可知选在中心点的位置是最好的,如果货仓是偶数的话,选在 [ a , b ] [a,b] [a,b]中的任意一点的结果都是一样的。
在这里插入图片描述

题目描述:

在一条数轴上有 N 家商店,它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。

为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

输入格式
第一行输入整数 N。
第二行 N 个整数 A1∼AN。

输出格式
输出一个整数,表示距离之和的最小值。

数据范围
1≤N≤100000,0≤Ai≤40000
输入样例:
4
6 2 9 1
输出样例:
12

示例代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 1e5+10;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> a[i];
    
    sort(a, a+n);
    
    int md = a[n>>1];
    LL res = 0;
    for(int i = 0; i < n; ++i)
    {
        res += abs(a[i] - md);
    }
    
    cout << res << endl;
    
    return 0;
}

四、耍杂技的牛(推公式)

思路:这个其实也就是从小到大排序,就是最优解了,也没什么为什么,能证出来,记住就行了。

题目描述:

农民约翰的 N 头奶牛(编号为 1..N)计划逃跑并加入马戏团,为此它们决定练习表演杂技。

奶牛们不是非常有创意,只提出了一个杂技表演:
叠罗汉,表演时,奶牛们站在彼此的身上,形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。

一头牛支撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值,现在称该数值为风险值
,风险值越大,这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序,使得所有奶牛的风险值中的最大值尽可能的小。

输入格式
第一行输入整数 N,表示奶牛数量。
接下来 N 行,每行输入两个整数,表示牛的重量和强壮程度,第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。

输出格式
输出一个整数,表示最大风险值的最小可能值。

数据范围
1≤N≤50000,1≤Wi≤10,000,1≤Si≤1,000,000,000
输入样例:
3
10 3
2 5
3 3
输出样例:
2

示例代码:

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int n;
PII cow[N];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        int w, s;
        cin >> w >> s;
        cow[i] = {w+s, w};
    }
    
    sort(cow, cow+n);
    
    LL res = -2e9, sum = 0;
    for(int i = 0; i < n; ++i)
    {
        int w = cow[i].y, s = cow[i].x - w;
        res = max(res, sum - s);
        sum += w;
    }
    
    cout << res << endl;
    
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/393653.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

《白话C++》第10章 STL和boost,Page73~74 boost::scoped_array

当所要创建的具体类型必须在运行时才能确定&#xff0c;此时需要使用new来实现动态创建&#xff1b; 另外还有一种&#xff1a;当需要一次性创建多个对象&#xff0c;但到底是几个无法在写代码时知道&#xff0c;需要在运行时动态创建&#xff0c;这种情况下也需要动态创建。此…

大数据,对于生活的改变

谷歌通过对于疾病的查询量可以预测一个个h1n1病毒的大爆发&#xff0c; 大数据时代对于人的考验 用户的搜索记录就是一种信息&#xff0c;这种信息会满足其基础相关的词条与其有关的词条&#xff08;最为原始的搜索机制&#xff0c;国内的搜索引擎都是采用这种基础原理。&…

柚见(伙伴匹配系统)第五期

后端个人信息接口 前端修改用户信息&#xff0c;点击提交&#xff1b;现在无法对接到后端&#xff0c;需要在后端新写一个接口/user/update。 控制层新增用户信息更新接口。 HttpServetRequest request: 前端的请求头中获取cookie,在后端查询登录态进行鉴权 User getLoginU…

化繁为简!用pytest编写接口自动化测试脚本的简易思路

引言 当今互联网时代&#xff0c;软件质量成为越来越重要的一个问题&#xff0c;而接口自动化测试是保障软件质量的一种关键手段。 在这个过程中&#xff0c;pytest成为了许多开发者的首选工具&#xff0c;既易于使用&#xff0c;又具有强大的功能。但是&#xff0c;对于初学…

C/C++ BM8 链表中倒数最后k个结点

文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言 这道题和BM1中的思路有些许类似&#xff0c;整体不难。 题目 描述 输入一个长度为 n 的链表&#xff0c;设链表中的元素的值为 ai &#xff0c;返回该链表中倒数第k个节点。 如果…

three.js 物体下落动画(重力加速度)

效果&#xff1a; <template><div><el-container><el-main><div class"box-card-left"><div id"threejs" style"border: 1px solid red"></div><el-button click"loopFun"> 物体下落…

效果图渲染为什么找「瑞云渲染」瑞云渲染邀请码WFQB

效果图的渲染可以通过个人的电脑&#xff0c;也可以通过第三方的云渲染平台&#xff0c;两者之间的区别很多人都知道是什么。如果用户需要使用个人电脑&#xff0c;通常需要搭配高性能的硬件&#xff0c;然而硬件中最贵的当数CPU、GPU&#xff0c;云渲染平台则是通过租用高配置…

day6:继承与多态

思维导图 2.编程题&#xff1a; 以下是一个简单的比喻&#xff0c;将多态概念与生活中的实际情况相联系&#xff1a;比喻&#xff1a;动物园的讲解员和动物表演 想象一下你去了一家动物园&#xff0c;看到了许多不同种类的动物&#xff0c;如狮子、大象、猴子等。现在&#xff…

Win32汇编数组学习2

之前学习过win32汇编数组&#xff1b;还不熟悉&#xff1b;继续熟悉&#xff1b; 先做几个基本的对话框&#xff0c;有一个静态文本框&#xff1b; 定义数组之后&#xff0c;用 wsprintf 函数格式化&#xff0c;然后调用 SetDlgItemText 赋值给静态文本框&#xff1b; arr1 …

[C++]二叉搜索树

一、定义 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根节点的值它的左右子树也分别…

深入浅出熟悉OpenAI最新大作Sora文生视频大模型

蠢蠢欲动&#xff0c;惴惴不安&#xff0c;朋友们我又来了&#xff0c;这个春节真的过的是像过山车&#xff0c;Gemini1.5 PRO还没过劲&#xff0c;OpenAI又放大招&#xff0c;人类真的要认输了吗&#xff0c;让我忍不住想要再探究竟&#xff0c;到底是什么让文生视频发生了质的…

C语言—指针

碎碎念:做指针题的时候我仿佛回到了原点&#xff0c;总觉得目的是为了把框架搭建起来&#xff0c;我胡说的哈31 1.利用指针变量将一个数组中的数据反向输出。 /*1.利用指针变量将一个数组中的数据反向输出。*/#include <stdio.h> #include <time.h> #include <…

常用类与基础API-String的理解和不可变性

1.String类的理解 1.1类的声明 public final class String >final &#xff1a;String是不可继承的。 >Serializable :可序列化的接口,凡是实现此接口的类的对象就可以通过网络或本地流进行数据的传输 >comparable:凡是实现此接口的类,其对象都可以比较大小. 1.…

【MySQL】多表关系的基本学习

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-3oES1ZdkKIklfKzq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…

基于8086单片机的数码管计时系统[proteus仿真]

基于8086单片机的数码管计时系统[proteus仿真] 8086仿真设计这个题目算是课程设计中常见的题目了&#xff0c;本期是一个基于8086单片机的数码管计时系统[proteus仿真] 需要的源文件和程序的小伙伴可以关注公众号【阿目分享嵌入式】&#xff0c;赞赏任意文章 2&#xffe5;&a…

Fiddler抓包(网页、手机、MUMU模拟器)

前置条件&#xff1a;电脑上下载安装好了Fiddler&#xff0c;有浏览器 一、网页抓包 1、fiddler下载安装证书 Tools-Options 勾选下面两个框 点击下面的选项&#xff0c;信任证书 会弹出弹窗&#xff0c;点击yes&#xff08;这个时候注意&#xff0c;DO_NOT_TRUST_FiddlerRo…

防御保护第五次作业

1,办公区设备可以通过电信链路和移动链路上网(多对多的NAT,并且需要保留一个公网IP不能用来转换) FW5&#xff1a; 2,分公司设备可以通过总公司的移动链路和电信链路访问到DMz区的http服务器 FW5&#xff1a; 注&#xff1a;记得通过安全策略放行 分公司FW3 注意&#xff1a…

Open CASCADE学习|曲线向曲面投影

在三维空间中&#xff0c;将曲线向曲面投影通常涉及复杂的几何计算。这个过程可以通过多种方法实现&#xff0c;但最常见的是使用数学和几何库&#xff0c;如OpenCASCADE&#xff0c;来处理这些计算。 在OpenCASCADE中&#xff0c;投影曲线到曲面通常涉及以下步骤&#xff1a;…

【plt.bar绘制条形图】:从入门到精通,只需一篇文章!【Matplotlib】

【&#x1f4ca;plt.bar绘制条形图】&#xff1a;从入门到精通&#xff0c;只需一篇文章&#xff01;【Matplotlib】 利用Matplotlib进行数据可视化示例 &#x1f335;文章目录&#x1f335; &#x1f50d; 一、初识plt.bar&#xff1a;条形图的基本概念&#x1f4a1; 二、plt.…

Spring Boot 笔记 025 主界面

1.1 路由搭建 1.1.1 安装vue router npm install vue-router4 1.1.2 在src/router/index.js中创建路由器&#xff0c;并导出 import { createRouter, createWebHistory } from vue-router//导入组件 import LoginVue from /views/Login.vue import LayoutVue from /views/La…