当前位置: 首页 > news >正文

牛客练习赛128:Cidoai的平均数对(背包dp)

题目描述

给定 nnn 对数 (ai,bi)(a_i,b_i)(ai​,bi​) 和参数 kkk,你需要选出一些对使得在满足 bib_ibi​ 的平均值不超过 kkk 的同时,aia_iai​ 的和最大,求出这个最大值。

输入描述:

第一行两个整数分别表示 n,kn,kn,k。
接下来 nnn 行,每行两个数分别表示 ai,bia_i,b_iai​,bi​

输出描述:

一行一个整数表示答案。

示例1

输入

复制5 6 4 10 3 4 6 7 7 7 10 8

5 6
4 10
3 4
6 7
7 7
10 8

输出

复制16

16

备注:

0≤ai,bi,k≤500,1≤n≤5000 \le a_i,b_i,k \le 500,1 \le n \le 5000≤ai​,bi​,k≤500,1≤n≤500

做法

本题重点在这个平均数的处理。b1+b2+b3+……+bn<=n*k,也就是(b1-k)+(b2-k)+(b3-k)+……+(bn-k)<=0。那我们就先把bi全都减去k。那bi为负数的就可以全部拿下。这样一来,我们背包的容量就是bi为负数的总和的绝对值了。

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=250010;
int n,k;
int a[N],b[N];
int dp[M];
int res,ans,sum,ans2;
struct ty{int a,b;
};
vector<ty> v;
int main(){scanf("%d%d",&n,&k);v.push_back({-1,-1});for(int i=1;i<=n;i++) {cin>>a[i]>>b[i];b[i]-=k;if(b[i]<=0) {ans+=a[i];sum+=-b[i];}else{v.push_back({a[i],b[i]});}}memset(dp,-0x3f,sizeof(dp));dp[0]=0;for(int i=1;i<v.size();i++){for(int j=sum;j>=0;j--){   if(j-v[i].b>=0)dp[j]=max(dp[j],dp[j-v[i].b]+v[i].a);}}for(int i=0;i<=sum;i++) ans2=max(dp[i],ans2);cout<<ans+ans2;
}

相关文章:

牛客练习赛128:Cidoai的平均数对(背包dp)

题目描述 给定 nnn 对数 (ai,bi)(a_i,b_i)(ai​,bi​) 和参数 kkk&#xff0c;你需要选出一些对使得在满足 bib_ibi​ 的平均值不超过 kkk 的同时&#xff0c;aia_iai​ 的和最大&#xff0c;求出这个最大值。 输入描述: 第一行两个整数分别表示 n,kn,kn,k。 接下来 nnn 行&…...

Python世界:简易地址簿增删查改算法实践

Python世界&#xff1a;简易地址簿增删查改算法实践 任务背景编码思路代码实现本文小结 任务背景 该任务来自简明Python教程中迈出下一步一章的问题&#xff1a; 编写一款你自己的命令行地址簿程序&#xff0c; 你可以用它浏览、 添加、 编辑、 删除或搜索你的联系人&#xff…...

网络安全-intigriti-0422-XSS-Challenge Write-up

目录 一、环境 二、解题 2.1看源码 一、环境 Intigriti April Challenge 二、解题 要求&#xff1a;弹出域名就算成功 2.1看源码 我们看到marge方法&#xff0c;肯定是原型链污染题目 接的是传参&#xff0c;我们可控的点在于qs.config和qs.settings&#xff0c;这两个可…...

Debian Linux 11 使用crash

文章目录 前言一、环境安装1.1 安装debug package1.2 安装crash 二、使用crash 前言 # cat /etc/os-release PRETTY_NAME"Debian GNU/Linux 11 (bullseye)" NAME"Debian GNU/Linux" VERSION_ID"11" VERSION"11 (bullseye)" VERSION_C…...

python列表 — 按顺序找出b表中比a表多出的元素

目录 一、功能描述 二、适用场景 三、代码实现 一、功能描述 有a、b两个列表&#xff0c;a列表有3个元素&#xff1b;b列表有7个元素。b列表多出的一个元素可能在随机的位置&#xff0c;在不影响其他元素的情况下&#xff0c;找到b列表多出的那四个元素&#xff0c;并按照在…...

如何使用Python创建目录或文件路径列表

在 Python 中&#xff0c;创建目录或生成文件路径列表通常涉及使用 os、os.path 或 pathlib 模块。下面是一些常见的任务和方法&#xff0c;用于在 Python 中创建目录或获取文件路径列表。 问题背景 在初始阶段的 Python 学习过程中&#xff0c;可能遇到这样的问题&#xff1a…...

领夹麦克风哪个品牌好,哪种领夹麦性价比高,无线麦克风推荐

在音频录制需求日益多样化的今天&#xff0c;无线领夹麦克风作为提升音质的关键设备&#xff0c;其重要性不言而喻。市场上鱼龙混杂&#xff0c;假冒伪劣、以次充好的现象屡见不鲜。这些产品往往以低价吸引消费者&#xff0c;却在音质、稳定性、耐用性等方面大打折扣&#xff0…...

苍穹外卖学习笔记(五)

文章目录 二.新增菜品1.图片上传2.具体新增菜品 二.新增菜品 1.图片上传 这里采用了阿里云oss对象存储服务 application.yml alioss:endpoint: ${sky.alioss.endpoint}access-key-id: ${sky.alioss.access-key-id}access-key-secret: ${sky.alioss.access-key-secret}bucket…...

什么是卷积层、池化层、BN层,有什么作用?

什么是卷积层、池化层、BN层&#xff0c;有什么作用&#xff1f; 卷积层池化层BN层 卷积层 定义&#xff1a; 卷积层是CNN中的核心组件&#xff0c;它通过卷积运算对输入数据进行特征提取。卷积层由多个卷积单元组成&#xff0c;每个卷积单元的参数通过反向传播算法优化得到。…...

[学习笔记]《CSAPP》深入理解计算机系统 - Chapter 4 处理器体系结构Chapter 5 优化程序性能

总结一些第四章和第五章的一些关键信息 Chapter 4 处理器体系结构将处理组织成阶段 Chapter 5 优化程序性能 Chapter 4 处理器体系结构 在硬件中&#xff0c;寄存器直接将它的输入和输出线连接到电路的其他盆。 在机器级变成中&#xff0c;寄存器代表的是 CPU 中为数不多的可寻…...

案例分享|我是这样转型做数据产品经理的?

本文为才聚学员投稿的原创作品&#xff0c;现在才聚正面向专业项目管理者征集“项目管理实战案例”原创文章&#xff0c;被采纳即可获得丰厚稿酬&#xff0c;欢迎大家关注公众号踊跃投稿。 如您有意向投稿&#xff0c;可将稿件投递给我们。 故事介绍 三段故事&#xff0c;讲…...

ffmpeg面向对象-rtsp拉流相关对象

目录 1.AVFormatContext和FFFormatContext类。1.1 概述1.2 构造函数1.3 oopc的继承实现 2. AVInputFormat 类。2.1 多态的实现 3.所用设计模式3.1模板模式3.2 工厂模式&#xff1f; 3.3 rtsp拉流建链 4.this指针5.小结6.rtsp拉流流程 1.AVFormatContext和FFFormatContext类。 …...

feign client发送Post请求,发送对象参数,服务端接收不到正确参数报错排查

记一次feignclient发送请求服务端接收不到正确参数排查 服务端代码&#xff1a; Operation(summary "Create team")PostMapping("post")RequiresPermissions("team:add")public RestResponse addTeam(Valid Team team) {this.teamService.crea…...

Hadoop林子雨安装

文章目录 hadoop安装教程注意事项&#xff1a; hadoop安装教程 链接: 安装教程 注意事项&#xff1a; 可以先安装ububtu增强功能&#xff0c;完成共享粘贴板和共享文件夹 ubuntu增强功能 2.这里就可以使用共享文件夹 或者在虚拟机浏览器&#xff0c;用 微信文件传输助手 传文…...

Springboot项目总结

1.为了调用写在其他包里面的类的方法 但是不使用new来实现调用这个类里面的方法&#xff0c;这个时候我们就需要将这个类注入到ioc容器里面&#xff0c;通过ioc容器来实现自动生成一个对象。 对ioc容器的理解&#xff1a;自动将一个对象实现new. 考察了and 和 or组合使用&…...

目标检测从入门到精通——数据增强方法总结

以下是YOLO系列算法&#xff08;从YOLOv1到YOLOv7&#xff09;中使用的数据增强方法的总结&#xff0c;包括每种方法的数学原理、相关论文以及对应的YOLO版本。 YOLO系列数据增强方法总结 数据增强方法数学原理相关论文图像缩放将输入图像缩放到固定大小&#xff08;如448x44…...

SQL server 的异常处理 一个SQL异常 如何不影响其他SQL执行

在 SQL Server 中&#xff0c;存储过程中的 SQL 语句是顺序执行的。如果其中任何一个 SQL 语句遇到了错误或异常&#xff0c;那么默认情况下&#xff0c;这个错误会导致整个事务&#xff08;如果有的话&#xff09;回滚&#xff0c;并且存储过程会立即停止执行&#xff0c;不会…...

STM32——看门狗通俗解析

笔者在学习看门狗的视频后&#xff0c;对看门狗仍然是一知半解&#xff0c;后面在实际应用中发现它是一个很好用的检测或者调试工具。所以总结一下笔者作为初学小白对看门狗的理解。 主函数初始化阶段、循环阶段和复位 众所周知&#xff0c;程序的运行一般是这样的&#xff1…...

点亮第一盏LED灯 5): stm32CubeMX生成Keil代码

嵌入式入门&#xff0c;继续点亮第一盏LED灯&#xff0c;前面文章已经配置了GPIO引脚和时钟&#xff0c;那么基本上stm32CubeMX的配置就完成了&#xff0c;还有一点就是可以对PC13这个引脚起个别名&#xff0c; 这里起的别名是 LED_PC13&#xff0c;还有注意地方就是GPIO mode…...

ollama语言大模型部署使用

ollama语言大模型部署使用 前言一、下载安装maxkb1、下载解压赋权2、安装 二、安装ollamadocker运行 三、无需获取api_keymaxkb安装ollama模型对&#xff0c;就是这&#xff0c;你选好基础模型后&#xff0c;只需要给他地址&#xff0c;添加完成后自行调用ollama安装你选择好的…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...