Peter算法小课堂—贪心与二分
太戈编程655题
题目描述:
有n辆车大甩卖,第i辆车售价a[i]元。有m个人带着现金来申请购买,第i个到现场的人带的现金为b[i]元,只能买价格不超过其现金额的车子。你是大卖场总经理,希望将车和买家尽量多地进行一对一配对,请问最多卖出多少辆车?
贪心
贪心法模板:
比如说:每次挑最便宜的车卖给贫穷的人,……
相信大家第一个想到的思路就是二重for循环,第一层int i=1;i<=m;i++,第二层int j=1;j<=n;j++,时间复杂度O(n^2)。但是一看数据规模,n,m<=200000,也就是运行40000000000,四百亿,几乎不可能。这一下子,大家就想到了传说中的“蠕动区间”。代码来咯,
#include <bits/stdc++.h>
using namespace std;
const int N=200009;
int n,m,a[N],b[N];
int main(){freopen("car2.in","r",stdin);freopen("car2.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];sort(a+1,a+1+n);sort(b+1,b+1+m);int cnt=0,i=1,j=1;while(i<=n&&j<=m){if(a[i]<=b[j]){i++;j++;cnt++;}else j++;}cout<<cnt<<endl;return 0;
}
太戈编程656题
题目描述:
有n辆车大甩卖,第i辆车售价a[i]元。有m个人带着现金来申请购买,第i个到现场的人带的现金为b[i]元。你是大卖场总经理,可以将车和买家自由配对。如果买家的现金低于配对车的售价时,你有权力借钱给买家,但是总的借款额度不可以超过f。注意:买家之间不会互相借钱。请问通过你的配对和借款,剩下没买到车的人最少有几人?
二分+贪心
思路:要让没买到车的人最少,相当于要求买到车的人最多。二分枚举答案x,OK函数判断卖出x辆车是否可行(最优化问题→可行性问题),而判断的方法就要用到贪心

bool OK(int x){int sum=0;for(int i=0;i<=x;i++){if(a[i]>b[m-x+i]) sum+=a[i]-b[m-x+i];if(sum>f) return 0; }return 1;
}
int main(){freopen("car3.in","r",stdin);freopen("car3.out","w",stdout);cin>>n>>m>>f;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<m;i++) cin>>b[i];sort(a,a+n);sort(b,b+m);int l=0,r=min(n,m),ans=0;while(l<=r){int mid=l+(r-l)/2;if(OK(mid)) ans=mid,l=mid+1;else r=mid-1;}cout<<m-ans<<endl;return 0;
}
太戈编程1662题
自己独立思考……
cin>>n>>d;
for(int i=1;i<=n;i++) cin>>x[i];
sort(x+1,x+n+1);
int cnt=0;
for(int i=1;j=2;i<=n-1;i++){while(j<=n&&x[j]-x[i]<d) j++;cnt+=j-i-1;
}
cout<<cnt<<endl;
希望这些对大家有用,三连必回
相关文章:
Peter算法小课堂—贪心与二分
太戈编程655题 题目描述: 有n辆车大甩卖,第i辆车售价a[i]元。有m个人带着现金来申请购买,第i个到现场的人带的现金为b[i]元,只能买价格不超过其现金额的车子。你是大卖场总经理,希望将车和买家尽量多地进行一对一配对…...
搭建Vue前端项目的流程
1、安装nodejs 测试安装是否成功 $ npm -v 6.14.16 $ node -v v12.22.122、全局安装npm install -g vue/cli,后续会使用到vue命令 $ vue --version vue/cli 5.0.8使用vue create demo_project_fe命令创建项目,使用箭头键来选择,确认使用回车…...
1.使用 Blazor 利用 ASP.NET Core 生成第一个 Web 应用
参考 https://dotnet.microsoft.com/zh-cn/learn/aspnet/blazor-tutorial/create 1.使用vs2022创建新项目 选择 C# -> Windows -> Blzxor Server 应用模板 2.项目名称BlazorApp下一步 3.选择 .NET6.0 或 .NET7.0 或 .NET8.0 创建 4.运行BlazorApp 5.全部选择是。 信…...
如何入门 GPT 并快速跟上当前的大语言模型 LLM 进展?
入门GPT 首先说第一个问题:如何入门GPT模型? 最直接的方式当然是去阅读官方的论文。GPT模型从2018年的GPT-1到现在的GPT-4已经迭代了好几个版本,通过官方团队发表的论文是最能准确理清其发展脉络的途径,其中包括GPT模型本身和一…...
【pentaho】kettle读取Hive表不支持bigint和timstamp类型解决。
一、bigint类型 报错: Unable to get value BigNumber(16) from database resultset显示kettle认为此应该是decimal类型(kettle中是TYPE_BIGNUMBER或称BigNumber),但实际hive数据库中是big类型。 修改kettle源码解决: kettle中java.sql.Types到kettle…...
centos 8 部署nextCloud
参考链接: Example installation on CentOS 8 — Nextcloud latest Administration Manual latest documentation 第一次 在RHEL 9.2部署,部署完成后,上传任意文件提示: 与服务器断开链接 发生未知错误 第二次 计划在centos…...
vue3 element-plus 输入框 clearable属性 聚焦时宽度会变化
解决办法 因为你的代码中el-input是没有宽度的, 所以实际渲染出来的 el-input宽度 原生input宽度 前缀图标宽度 后缀图标宽度。 可以写css固定el-input宽度来处理。 :deep.el-input.el-input--default.el-input--suffix {// 固定宽度width: 200px !important; …...
【科技前沿】数字孪生技术改革智慧供热,换热站3D可视化引领未来
换热站作为供热系统不可或缺的一部分,其能源消耗对城市环保至关重要。在双碳目标下,供热企业可通过搭建智慧供热系统,实现供热方式的低碳、高效、智能化,从而减少碳排放和能源浪费。通过应用物联网、大数据等高新技术,…...
Vue.js 教程
Vue.js(读音 /vjuː/, 类似于 view) 是一套构建用户界面的渐进式框架。 Vue 只关注视图层, 采用自底向上增量开发的设计。 Vue 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。 阅读本教程前,您需要了解的…...
听GPT 讲Rust源代码--src/tools(21)
File: rust/src/tools/miri/src/shims/x86/mod.rs 在Rust的源代码中,rust/src/tools/miri/src/shims/x86/mod.rs文件的作用是为对x86平台的处理提供支持。它包含一些用于模拟硬件操作的shim函数和相关的类型定义。 具体来说,该文件中的函数是通过使用一组…...
OpenCV | 告别人工目检:深度学习技术引领工业品缺陷检测新时代
文章目录 机器视觉缺陷检测工业上常见缺陷检测方法内容简介作者简介目录读者对象如何阅读本书获取方式 机器视觉 机器视觉是使用各种工业相机,结合传感器跟电气信号实现替代传统人工,完成对象识别、计数、测量、缺陷检测、引导定位与抓取等任务。其中工…...
Inkscape SVG 编辑器 导入 Gazebo
概述 本教程描述了拉伸 SVG 文件的过程,这些文件是 2D 的 图像,用于在 Gazebo 中为您的模型创建 3D 网格。有时是 更容易在 Inkscape 或 Illustrator 等程序中设计模型的一部分。 在开始之前,请确保您熟悉模型编辑器。 本教程将向您展示如…...
基于比较的排序算法总结(java实现版)
目录 什么是基于比较的排序算法 什么是排序算法的稳定性 基础排序算法的稳定性 插入排序法 希尔排序法 冒泡排序法 总结 高级算法的稳定性 快速排序法 堆排序法 归并排序法 总结 注意 什么是基于比较的排序算法 基于比较的排序算法定义:之所以能给元素…...
集群与分布式的概念及区别
目前在工作中经常接触到集群的概念,通过这篇文章总结一下集群的几种方式以及和分布式对比学习 1.集群(Cluster) 集群是由多个计算机节点组成的网络,旨在共同提供服务,并确保高性能和高可用性。在高可用集群中…...
基于ssm+vue的在线听书网站论文
摘 要 传统信息的管理大部分依赖于管理人员的手工登记与管理,然而,随着近些年信息技术的迅猛发展,让许多比较老套的信息管理模式进行了更新迭代,书籍信息因为其管理内容繁杂,管理数量繁多导致手工进行处理不能满足广大…...
hive命令启动出现classnotfound
环境:ambari集群三个节点node104、node105和node106,其中node105上有hiveserver2,并且三个节点均有HIVE CLIENT 注意:“./”指hive安装目录 其中装有hiveserver2的node105节点,由于某种需要向lib目录下上传了某些jar包…...
拥抱数字化转型,共赢数字时代 | 创维汽车商学院走进竹云
数字化浪潮汹涌而来,变革与创新接踵而至。随着数字技术日益融入经济社会发展的各个领域,数字经济与实体经济的“双向奔赴”也不断催生着新产业、新业态、新模式,为经济社会发展持续注入创新活力。12月19日,创维汽车商学院带领嘉宾…...
蓝桥杯:日期问题
目录 引言一、日期问题1.题目描述2.代码实现3.测试 二、回文日期1.题目描述2.代码实现3.测试 引言 关于这个蓝桥杯的日期问题,其实有一个明确的思路就感觉很简单,这个思路就是不用依照日期的顺序去把每一天走完,而是根据一个数加一ÿ…...
vue 简单实现购物车:商品基础信息最终的 html 文件 + 商品计数器的组件处理,实现了购物车;
购物车实现过程: Ⅰ、商品购物车作业需求:1、商品购物车页面示例:2、具体需求: Ⅱ、html 文件的构建:商品购物车.html Ⅲ、组件文件的构建:商品购物车1.js Ⅳ、小结: Ⅰ、商品购物车作业需求&am…...
交叉熵损失(Cross Entropy Loss)学习笔记
在分类任务中,我们通常使用交叉熵作为损失函数,首先给出交叉熵的计算公式: 二分类中: L 1 N ∑ i L i 1 N ∑ i − [ y i l o g ( p i ) ( 1 − y i ) ⋅ l o g ( 1 − p i ) ] \mathcal{L}\frac1{N}\sum_{i}L_i\frac1{N}\sum…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
