[Algorithm][综合训练][消减整数][最长上升子序列(二)][春游]详细讲解

本文主要是介绍[Algorithm][综合训练][消减整数][最长上升子序列(二)][春游]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1.消减整数
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 2.最长上升子序列(二)
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 3.春游
    • 1.题目链接
    • 2.算法原理详解 && 代码实现


1.消减整数

1.题目链接

  • 消减整数

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

  • 解法:贪心 + 数学
    • 每次尽可能的减去之前数的两倍,并且能保证可以减到0
    • x % 2a == 0
    #include <iostream>
    using namespace std;int Check(int h)
    {int ret = 0, a = 1;while(h){ret++;h -= a;if(h % (2 * a) == 0){a *= 2;}}return ret;
    }int main()
    {int n = 0, h = 0;cin >> n;while(n--){cin >> h;cout << Check(h) << endl;}
    }
    

2.最长上升子序列(二)

1.题目链接

  • 最长上升子序列(二)

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

  • 自己的版本:动态规划 -> 50%
    int LIS(vector<int>& nums) 
    {int n = nums.size();vector<int> dp(n, 1);int ret = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;
    }
    
  • 优化版本:贪心 + 二分
    • 不关心前面的非递减子序列长什么样子,仅需知道长度为x的子序列末尾是多少即可
    • 存长度为x的所有子序列的末尾时,只用存最小的那个数即可
    • 优化:二分快速寻找插入位置
    int LIS(vector<int>& a)
    {int pos = 0;vector<int> dp(a.size() + 1, 0); // dp[i]: 长度为i的最小末尾// 查找x应该放在哪个位置for(const auto& x : a){// 边界情况处理if(pos == 0 || x > dp[pos]){dp[++pos] = x;}else{// 二分查找插入位置int l = 1, r = pos;while(l < r){int mid = (l + r) / 2;if(dp[mid] >= x){r = mid;}else{l = mid + 1;}}dp[l] = x;}}return pos;
    }
    

3.春游

1.题目链接

  • 春游

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

  • 解法:贪心 + 分类讨论 --> 细致讨论即可,容易疏漏
    请添加图片描述

    #include <iostream>
    using namespace std;long long n = 0, a = 0, b = 0;long long CostTotal(char ch)
    {long long sum = 0;if(ch == 'a'){sum = n / 2 * a;n %= 2;if(n){sum += min(min(a, b), b - a);}}else{sum = n / 3 * b;n %= 3;if(n == 1){sum += min(min(a, b), 2 * a - b);}else if(n == 2){sum += min(min(a, b), 3 * a - b);}}return sum;
    }int main()
    {int t = 0;cin >> t;while(t--){cin >> n >> a >> b;float av = a / 2.0, bv = b / 3.0;if(n <= 2){cout << min(a, b) << endl;continue;}if(av < bv){cout << CostTotal('a') << endl;}else{cout << CostTotal('b') << endl;}}return 0;
    }
    

这篇关于[Algorithm][综合训练][消减整数][最长上升子序列(二)][春游]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Spring Boot Actuator应用监控与管理的详细步骤

《SpringBootActuator应用监控与管理的详细步骤》SpringBootActuator是SpringBoot的监控工具,提供健康检查、性能指标、日志管理等核心功能,支持自定义和扩展端... 目录一、 Spring Boot Actuator 概述二、 集成 Spring Boot Actuat

如何在Java Spring实现异步执行(详细篇)

《如何在JavaSpring实现异步执行(详细篇)》Spring框架通过@Async、Executor等实现异步执行,提升系统性能与响应速度,支持自定义线程池管理并发,本文给大家介绍如何在Sprin... 目录前言1. 使用 @Async 实现异步执行1.1 启用异步执行支持1.2 创建异步方法1.3 调用

Spring Boot 与微服务入门实战详细总结

《SpringBoot与微服务入门实战详细总结》本文讲解SpringBoot框架的核心特性如快速构建、自动配置、零XML与微服务架构的定义、演进及优缺点,涵盖开发环境准备和HelloWorld实战... 目录一、Spring Boot 核心概述二、微服务架构详解1. 微服务的定义与演进2. 微服务的优缺点三

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析(结合应用场景)

《nginx-t、nginx-sstop和nginx-sreload命令的详细解析(结合应用场景)》本文解析Nginx的-t、-sstop、-sreload命令,分别用于配置语法检... 以下是关于 nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析,结合实际应

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap