[Algorithm][综合训练][比那名居的桃子][chika和蜜柑][礼物的最大价值]详细讲解

目录

  • 1.比那名居的桃子
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 2.chika和蜜柑
    • 1.题目链接
    • 2.算法原理详解 && 详细讲解
  • 3.礼物的最大价值
    • 1.题目链接
    • 2.算法原理详解 && 代码实现


1.比那名居的桃子

1.题目链接

  • 比那名居的桃子

2.算法原理详解 && 代码实现

  • 自己的版本:暴力解法 --> 超时 37.5%
    #include <iostream>
    #include <vector>
    using namespace std;int main()
    {int n = 0, k = 0;cin >> n >> k;vector<int> happy(n, 0), shame(n, 0);for(int i = 0; i < n; i++){cin >> happy[i];}for(int i = 0; i < n; i++){cin >> shame[i];}vector<vector<int>> ret(n, vector<int>(2, 0));for(int i = 0; i < n; i++) // 枚举每个起点{for(int j = 0; j < k; j++){if(i + j < n){ret[i][0] += happy[i + j];ret[i][1] += shame[i + j];}}}int day = 0, happyMax = 0;for(int i = 0; i < n; i++){// 目标是:尽可能多的快乐值if(happyMax < ret[i][0]){happyMax = ret[i][0];day = i;}// 快乐值相等 -->  尽可能少的羞耻度if(happyMax == ret[i][0]){if(ret[i][1] < ret[day][1]){day = i;}}// 快乐值 == 羞耻度 -->  尽可能早的吃桃子// 不更新值就可以}cout << day + 1<< endl;return 0;
    }
    
  • 优化版本1:滑动窗口
    #include <iostream>
    #include <vector>
    using namespace std;int main()
    {int n = 0, k = 0;cin >> n >> k;vector<int> happy(n, 0), shame(n, 0);for(int i = 0; i < n; i++){cin >> happy[i];}for(int i = 0; i < n; i++){cin >> shame[i];}int left = 0, right = 0;long long hSum = 0, sSum = 0, hMax = 0, sMin = 0, begin = 0;while(right < n){hSum += happy[right];sSum += shame[right];while(right - left + 1 > k){hSum -= happy[left];sSum -= shame[left];left++;}if(right - left + 1 == k){if(hSum > hMax){begin = left;hMax = hSum;sMin = sSum;}else if(hSum == hMax && sSum < sMin){                begin = left;sMin = sSum;}}right++;}cout << begin + 1<< endl;return 0;
    }
    
  • 优化版本2:前缀和

2.chika和蜜柑

1.题目链接

  • chika和蜜柑

2.算法原理详解 && 详细讲解

  • 优化版本:排序/TOP-K --> 堆/数组模拟均可 --> 自定排序规则
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;typedef pair<int, int> PII;int main()
    {int n = 0, k = 0;cin >> n >> k;vector<PII> orgs(n); // <sour, sweet>for(int i = 0; i < n; i++){cin >> orgs[i].first;}for(int i = 0; i < n; i++){cin >> orgs[i].second;}sort(orgs.begin(), orgs.end(), [&](const PII& p1, const PII& p2){if(p1.second != p2.second){return p1.second > p2.second;}else{return p1.first < p2.first;}});long long sour = 0, sweet = 0;for(int i = 0; i < k; i++){sour += orgs[i].first;sweet += orgs[i].second;}cout << sour << " " << sweet << endl;return 0;
    }
    

3.礼物的最大价值

1.题目链接

  • 礼物的最大价值

2.算法原理详解 && 代码实现

  • 自己的版本:暴搜 --> 超时
    class Solution 
    {
    public:int dx[2] = {1, 0}; int dy[2] = {0, 1};int n = 0, m = 0, cnt = 0, ret = 0;int maxValue(vector<vector<int> >& grid) {n = grid.size(), m = grid[0].size();DFS(grid, grid[0][0], 0, 0);return ret;}void DFS(vector<vector<int> >& grid, int cnt, int x, int y){if(x == n - 1 && y == m - 1){ret = max(cnt, ret);}for(int k = 0; k < 2; k++){int a = x + dx[k], b = y + dy[k];if(a < n && b < m){DFS(grid, cnt + grid[a][b], a, b);}}}
    };
    
  • 优化版本:动态规划 – 路径问题
    int maxValue(vector<vector<int> >& grid)
    {int n = grid.size(), m = grid[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));for(int i = 1; i <=n; i++){for(int j = 1; j <= m; j++){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];}}return dp[n][m];
    }
    

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

WEB服务器-Nginx源码安装及相关配置

一、web服务的常用种类 Apache HTTP Server 简介&#xff1a;Apache是一款广泛使用的Web服务器软件&#xff0c;支持多种操作系统&#xff0c;包括Linux。​​​​​​​特点&#xff1a; 支持多个虚拟主机。 模块化架构&#xff0c;可以根据需要加载不同的模块。 强大的安全…

多态(虚构的整体,具体的个体)(多态的基本概念/多态的原理剖析/纯虚函数和抽象类/虚析构和纯虚析构)

多态的基本概念 #define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; // 多态的基本概念 // 多态分为静态多态和动态多态 // 静态多态&#xff1a; 函数重载还运算符重载属于静态多态&#xff0c;服用函数名 // 动态多态&#xff1a; 派生派和虚函…

VUE使用websocket

在之前搭建好的项目的基础上新版security demo&#xff08;二&#xff09;前端-CSDN博客 目录 一、代码改造 1、后端改造 2、VUE使用websocket 3、测试 二、按用户推送 1、完整代码如下 1.1、前端 1.2、后端&#xff1a; 2、测试 一、代码改造 1、后端改造 &#x…

逆波兰表达式

简介 介绍逆波兰表达式之前&#xff0c;先介绍一下运算种类。 中缀运算与后缀运算 中缀运算是一种常用的算术和逻辑公式表示方法&#xff0c;其中操作符位于两个运算数之间。例如&#xff0c;在表达式 “3 2” 中&#xff0c;加号&#xff08;&#xff09;是操作符&#xf…

算法设计:实验一分治与递归

【实验目的】 深入理解分治法的算法思想&#xff0c;应用分治法解决实际的算法问题。 【实验内容与要求】 设有n2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表&#xff1a; 1.每个选手必须与其他n-1个选手各赛一次&#xff1b;2.每个选手一天只能赛一…

Mysql 集群技术

目录 一 Mysql 在服务器中的部署方法 1.1 在Linux下部署mysql 1.1.1 安装依赖性并解压源码包&#xff0c;源码编译安装mysql&#xff1a; 1.1.2 部署mysql 二 mysql的组从复制 2.1 配置mastesr和salve 测试结果 2.2 当有数据时添加slave2 2.3 延迟复制 2.4 慢查询日志…

【C++ | 设计模式】简单工厂模式的详解与实现

1.简单工厂模式概述 简单工厂模式&#xff08;Simple Factory Pattern&#xff09;是一种创建型设计模式&#xff0c;它定义了一个工厂类&#xff0c;由这个类根据提供的参数决定创建哪种具体的产品对象。简单工厂模式将对象的创建逻辑集中到一个工厂类中&#xff0c;从而将对…

Python-进阶-Excel基本操作

文章目录 Excel 基本操作1. 概述2. 写入2.1 使用 xlwt2.2 使用 XlsxWriter 3. 读取4. 修改 Excel 基本操作 1. 概述 在数据处理方面&#xff0c;Python 一直扮演着重要的角色&#xff0c;对于 Excel 操作&#xff0c;它有着完整且成熟的第三方库&#xff0c;使用也较为简单。…

视频结构化从入门到精通——认识视频结构化

认识视频结构化 1. 视频结构化与非结构化 1. 非结构化数据 非结构化数据指的是未经处理、以原始形式存在的数据。这类数据是直接采集、记录的&#xff0c;包含了音频、视频等多维信息&#xff0c;且没有任何标签、注释或分类来表示其中的内容。非结构化数据需要进一步处理和…

AI视频平台精选:国内外对比与推荐

原文&#xff1a;AI视频平台精选&#xff1a;国内外对比与推荐 国内外有多个平台可以生成AI视频&#xff0c;这些平台各有其独特的优点和缺点。以下是对一些主要平台的详细介绍&#xff0c;包括它们的优缺点&#xff0c;以及针对个人和自媒体用户的推荐。 国内平台 1. 快手可…

Android 架构模式之 MVVM

Android 架构 Android 架构模式之 MVCAndroid 架构模式之 MVPAndroid 架构模式之 MVVM 目录 Android 架构架构设计的目的对 MVVM 的理解代码ModelViewViewModel Android 中 MVVM 的问题试吃个小李子BeanModelViewViewModel效果展示 大家好&#xff01; 作为 Android 程序猿&a…

代码随想录算法训练营第13天 |二叉树的学习

目录 二叉树 理论基础 二叉树的分类 1. 满二叉树 (Full Binary Tree) 2. 完全二叉树 (Complete Binary Tree) 3. 平衡二叉树 (Balanced Binary Tree) 5. 二叉搜索树 (Binary Search Tree, BST) 二叉树的存储 1. 链式存储 (Linked Representation) 2. 顺序存储 (Sequent…

Golang | Leetcode Golang题解之第363题矩形区域不超过K的最大数值和

题目&#xff1a; 题解&#xff1a; import "math/rand"type node struct {ch [2]*nodepriority intval int }func (o *node) cmp(b int) int {switch {case b < o.val:return 0case b > o.val:return 1default:return -1} }func (o *node) rotate…

pyro 教程 时间序列 单变量,重尾,python pytorch,教程和实例 Forecasting预测,布朗运动项、偏差项和协变量项

预测I:单变量&#xff0c;重尾 本教程介绍了预测模块&#xff0c;用Pyro模型进行预测的框架。本教程只涵盖单变量模型和简单的可能性。本教程假设读者已经熟悉慢病毒感染和张量形状. 另请参见: 预测II:状态空间模型 预测三:层次模型 摘要 要创建预测模型: 创建预测模型班级…

算法笔试-编程练习-H-02-24

w这套题&#xff0c;侧重模拟和题目理解&#xff0c;只要按照题目描述正常复现整体分数应该不错 一、数据重删 数据重删是一种节约存储空间的技术&#xff0c;通常情况下&#xff0c;在数据存储池内是有很多重复的数据库。重删则是将这些重复的数据块找出并处理的技术。简单地…

Java:jdk8之后新增的时间API

文章目录 为什么要使用新增的API新增了哪些&#xff1f;Local常用方法代码一样的用法 黑马学习笔记 使用新增的 为什么要使用新增的API 新增了哪些&#xff1f; Local 常用方法 代码 package NewTime;import java.time.LocalDate;/*** Author: ggdpzhk* CreateTime: 2024-08-…

竞猜足球核心算法源码

需要实现的功能如下&#xff1a; 仅用于学习 竞猜足球核心算法源码 package com.lotterysource.portsadmin.service; import com.aliyun.oss.common.utils.DateUtil; import com.fasterxml.jackson.core.type.TypeReference; import com.lotterysource.portsadmin.dbprovid…

@ohos.systemParameterEnhance系统参数接口调用:控制设备硬件(执行shell命令方式)

本文介绍如何使用应用ohos.systemParameterEnhance (系统参数)(系统接口)来控制设备硬件&#xff0c;可以通过它在系统中执行一段shell命令&#xff0c;从而实现控制设备的效果。接下来以一个实际的样例来演示如何通过它来控制设备以太网接口 开源地址&#xff1a;https://git…

链表OJ题——环形链表2

文章目录 一、题目链接二、解题思路三、解题代码 一、题目链接 环形链表2 题目描述&#xff1a;在链表有环的基础上&#xff0c;找出环的入口点。 二、解题思路 三、解题代码

超实用的8个无版权、免费、高清图片素材网站整理

不管是设计、文章配图&#xff0c;还是视频制作&#xff0c;图片都至关重要。但是图片版权一直都是困扰很多设计、自媒体以及企业的大问题。现在&#xff0c;因为图片侵权被告的案例已经是司空见惯了&#xff0c;有的公众号甚至因为图片版权问题遭受致命打击。 1. Pexels Pexe…