当前位置: 首页 > 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安装你选择好的…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...