[c++刷题]贪心算法.N01

题目如上:

首先通过经验分析,要用最少的减半次数,使得数组总和减少至一半以上,那么第一反应就是每次都挑数组中最大的数据去减半,这样可以是每次数组总和值减少程度最大化。

代码思路:利用大根堆去找数据中的最大值,每次减半再次压入大根堆即可。

主要是如何证明贪心策略的正确性 :

我们使用《交换论证法》来证明

圆圈代表每次减半的数,圆圈的个数就代表总操作次数。

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

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

相关文章

LeetCode | 520.检测大写字母

这道题直接分3种情况讨论:1、全部都为大写;2、全部都为小写;3、首字母大写其余小写。这里我借用了一个全是大写字母的串和一个全为小写字母的串进行比较 class Solution(object):def detectCapitalUse(self, word):""":type …

LeetCode347:前K个高频元素

题目描述 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 解题思想 使用优先队列 priority_queue<Type, Container, Functional> Type 就是数据类型&#xff0c;Container 就是容器类型&#xff08;C…

unity跑酷游戏(源码)

包括&#xff1a;触发机关&#xff0c; 优化 fog的调试 效果 碰到障碍物游戏时间暂停&#xff08;挂载到障碍物上&#xff09; 上面需要有碰撞体 游戏物体上需要有标签 using System.Collections; using System.Collections.Generic; using UnityEngine;public class Barri…

C语言----数据在内存中的存储

1.整数在内存中的存储 对整数来说&#xff1a;数据存放内存中其实存放的是二进制的补码 正整数的原反补码都相同 负数就不一样了 计算的使用的是内存中存放的二进制&#xff0c;计算使用的就是补码 2.大小端字节和字节序判断 其实超过一个字节的数据在内存中存的时候&…

Tensorflow-GPU工具包了解和详细安装方法

目录 基础知识信息了解 显卡算力 CUDA兼容 Tensorflow gpu安装 CUDA/cuDNN匹配和下载 查看Conda driver的版本 下载CUDA工具包 查看对应cuDNN版本 下载cuDNN加速库 CUDA/cuDNN安装 CUDA安装方法 cuDNN加速库安装 配置CUDA/cuDNN环境变量 配置环境变量 核验是否安…

Spring-kafka消费者消费的一些问题

前言 Spring Kafka 无缝集成了 Spring Boot、Spring Framework 及其生态系统中的其他项目&#xff0c;如 Spring Cloud。通过与 Spring Boot 的自动配置结合&#xff0c;开发者可以快速启动和配置 Kafka 相关的功能。无需编写大量样板代码即可实现 Kafka 的生产和消费功能&…

C++ Primer Plus第五版笔记(p201-250)

第六章 函数&#xff08;下&#xff09; 在含有return语句的循环后面应该也有一条return语句 不要返回局部对象的引用或指针&#xff0c;当函数结束时临时对象占用的空间也就随之释放掉了&#xff0c;所以两条return语句都指向了不再可用的内存空间。 如果函数返回指针、引用…

解决使用Jmeter进行测试时出现“302“,‘‘401“等用户未登录的问题

使用 JMeter 压力测试时解决登录问题的两种方法 在使用 JMeter 进行压力测试时&#xff0c;可能会遇程序存在安全验证&#xff0c;必须登录后才能对里面的具体方法进行测试&#xff1a; 如果遇到登录问题&#xff0c;通常是因为 JMeter 无法模拟用户的登录状态&#xff0c;导…

Windows NT 3.5程序员讲述微软标志性“3D管道”屏幕保护程序的起源故事

人们使用屏保程序来防止 CRT 显示器"烧毁"&#xff0c;因为静态图像会永久损坏屏幕。像 3D Pipes 这样的屏保程序能在显示器处于非活动状态时为其提供动画效果&#xff0c;从而保护屏幕并延长其使用寿命。此外&#xff0c;它们还能在用户不使用电脑时为其提供可定制的…

云计算【第一阶段(14)】Linux的目录和结构

一、Liunx目录结构 1.1、linux目录结构 linux目录结构是树形目录结构 根目录&#xff08;树根&#xff09; 所有分区&#xff0c;目录&#xff0c;文件等的位置起点整个树形目录结构中&#xff0c;使用独立的一个"/",表示 1.2、常见的子目录 必须知道 目录路径目…

Java | Leetcode Java题解之第147题对链表进行插入排序

题目&#xff1a; 题解&#xff1a; class Solution {public ListNode insertionSortList(ListNode head) {if (head null) {return head;}ListNode dummyHead new ListNode(0);dummyHead.next head;ListNode lastSorted head, curr head.next;while (curr ! null) {if (…

【elementui源码解析】如何实现自动渲染md文档-第三篇

目录 1.前言 2.webpack.demo.js 3.markdown文档 4.fence.js 1&#xff09;tokens 2&#xff09;::: 3&#xff09; 5.containers.js 1&#xff09;markdown-it-container 2&#xff09;md.use() 3&#xff09;代码逻辑 4&#xff09;containers小结 6.congfig.js …

qt dll编写和调用

dll编写 新建项目 头文件 #ifndef LIB1_H #define LIB1_H#include "lib1_global.h"class LIB1_EXPORT Lib1 { public:Lib1(); };//要导出的函数&#xff0c;使用extern "C"&#xff0c;否则名称改变将找不到函数extern "C" LIB1_EXPORT int ad…

基于单片机的无线遥控自动翻书机械臂设计

摘 要&#xff1a; 本设备的重点控制部件为单片机&#xff0c;充分实现了其自动化的目的。相关研究表明&#xff0c;它操作简单便捷&#xff0c;使残疾人在翻书时提供了较大的便利&#xff0c;使用价值性极高&#xff0c;具有很大的发展空间。 关键词&#xff1a; 机械臂&…

C++语法13 单分支结构的相关问题详解

一、奇偶数问题 要判断一个数是否是偶数&#xff0c;只要判断这个数字能不能被2整除即可。如果一个数字a除以2&#xff0c;没有余数&#xff0c;那么就是偶数&#xff1b;如果除以2有余数&#xff0c;那么就是奇数。 if(a%20) a是偶数 if(a%21) a是奇数 训练&#xff1…

PySide(PyQt)实现鼠标画框局部放大

按住鼠标左键画框&#xff0c;裁切画面并局部放大&#xff0c;可以用来生成ROI 1、在QtDesigner中创建ui文件&#xff0c;命名为crop.ui&#xff1a; 2、自定义脚本ImageLabel.py &#xff1a; from PySide6.QtCore import Qt, QRect, Signal, QPoint from PySide6.QtGui impo…

[C++] 从零实现一个ping服务

&#x1f4bb;文章目录 前言ICMP概念报文格式 Ping服务实现系统调用函数具体实现运行测试 总结 前言 ping命令&#xff0c;因为其简单、易用等特点&#xff0c;几乎所有的操作系统都内置了一个ping命令。如果你是一名C初学者&#xff0c;对网络编程、系统编程有所了解&#xff…

【unity笔记】二、海洋系统Crest Ocean System基础

1. 创建海平面 首先确定项目中导入了HDRP插件。这里使用Crest Ocean System HDRP插件。 在场景下创建空对象&#xff0c;这里命名为Ocean。将 OceanRenderer 组件分配给Ocean。该组件将生成海洋几何图形并执行所有必需的初始化。其中Global Wind Speed 属性可以调节风浪大小。…

[BSidesCF 2020]Had a bad day1

看到页面有两个按钮 先随便点一个试一下&#xff0c;当我们点击之后发现url是有变动的 感觉url是有点东西的&#xff0c;可能是某种注入&#xff0c;先尝试一下sql注入&#xff0c;发现给出了报错 通过报错我们可以确定是文件包含漏洞&#xff0c;那我们试试php伪协议去读取一下…

HarmongOS打包[保姆级]

创建应用 首先进入 华为开发者联盟-HarmonyOS开发者官网 然后进行登录。 登录成功后&#xff0c;鼠标悬停在在登录右上角那个位置后再点击管理中心&#xff0c;进入下面这个界面。 再点击&#xff1a;应用服务–>应用发布–>新建–>完善信息 构建和生成私钥和证书请求…