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

AcWing171.送礼物

题目描述

达达帮翰翰给女生送礼物,翰翰一共准备了NNN 个礼物,其中第 iii 个礼物的重量是 G[i]G[i]G[i]

达达的力气很大,他一次可以搬动重量之和不超过 WWW 的任意多个物品。

达达希望一次搬掉尽量重的一些物品,请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数,分别代表 WWWNNN

以后 N 行,每行一个正整数表示 G[i]G[i]G[i]

输出格式

仅一个整数,表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围

1≤N≤461 \le N \le 461N46
1≤W,G[i]≤231−11 \le W,G[i] \le 2 ^ {31} - 11W,G[i]2311

输入样例

20 5
7
5
4
18
1

输出样例

19

思路

由于取得方法有2462^{46}246(70368744177664)种,肯定超时。但如果将其分成两组,每组就只有2232^{23}223(8388608)种,这就可以过了。先将第一组可能组成的数存入数组(要去重,不然TLE),然后再枚举第二组,枚举到一个数就二分搜索与第一组可以组成最大的数。

代码

#include <iostream>
#include <algorithm>
using namespace std;int n, w, k;
int a[50];
int pp[16777216], p[16777216], cnt, cnt1, ans;bool cmp(int x, int y)
{return x > y;
}void dfs1(int step, int last) 
{if (step == n / 2) {pp[cnt++] = last;return;}if ((long) last + a[step] <= w) dfs1(step + 1, last + a[step]);dfs1(step + 1, last);
}void dfs2 (int step, int last) 
{if (step == n) {int l = 0, r = cnt - 1;while(l < r) {int mid = (l + r + 1) / 2;if ((long) p[mid] + last <= w) l = mid;else r = mid - 1;}if ((long) p[l] + last <= w) ans = max(ans, p[l] + last);return;}if ((long) last + a[step] <= w) dfs2(step + 1, last + a[step]);dfs2(step + 1, last);
}int main() {cin >> w >> n;for (int i = 0; i < n; i++) cin >> a[i];sort(a, a + n, cmp);k = n / 2;dfs1(0, 0);sort(pp, pp + cnt);int cnt1 = cnt;cnt = 0;for (int i = 1; i <= cnt1; i++){if (pp[i] != pp[i - 1]) p[++cnt] = pp[i];}dfs2(n / 2, 0);cout << ans << endl;return 0;
}

相关文章:

AcWing171.送礼物

题目描述 达达帮翰翰给女生送礼物&#xff0c;翰翰一共准备了NNN 个礼物&#xff0c;其中第 iii 个礼物的重量是 G[i]G[i]G[i]。 达达的力气很大&#xff0c;他一次可以搬动重量之和不超过 WWW 的任意多个物品。 达达希望一次搬掉尽量重的一些物品&#xff0c;请你告诉达达在…...

领域驱动设计-架构篇

目录 1、软件架构概述 1.1 软件架构概念 1.2 软件架构分类 1.3 软件架构模式 1.4 软件架构风格 2、领域驱动软件架构 2.1 架构风格 六边行架构&#xff08;领域驱动设计首选&#xff09; 为什么选择REST架构 松耦合 可伸缩性 易用性 约束性 2.2 架构模型 命令和…...

docker安装kafka

前言最近在用kafka做项目&#xff0c;所以本地搭建下kafka&#xff0c;但是又嫌java安装和安装kafka太麻烦&#xff0c;所以想到用docker来部署。镜像wurstmeister/kafka维护较为频繁的一个Kafka镜像。只包含了Kafka&#xff0c;因此需要另行提供ZooKeeper&#xff0c;推荐使用…...

Selenium4+Python3系列(十一) - Page Factory设计模式

写在前面&#xff1a; Page Object模式&#xff0c;目的是将元素定位和元素操作分层&#xff0c;只接触测试内容&#xff0c;不写基础内容&#xff0c;便于后续对自动化测试用例体系的维护&#xff0c;这是中心思想&#xff0c;也是核心。 那么我们继续将简洁延续&#xff0c…...

C++基础知识【4】函数及参数

目录 一、函数的基本概念 1.1、构成 1.2、声明和定义 1.3、函数的调用 二、参数 2.1、形参和实参 2.2、参数的传递 传值 传引用 传指针 三、C函数的一些新特性 3.1、Lambda表达式 3.2、右值引用 3.3、默认参数 3.4、变长参数模板 3.5、constexpr函数 3.6、noex…...

约瑟夫森磁效应

电流与波函数的相位有直接的关系&#xff0c;可得约瑟夫森结的电流为 IIcsinϕ\begin{align} II_c sin\phi \end{align} IIc​sinϕ​​ 式中&#xff0c;IcI_cIc​为临界电流&#xff0c;相位差为ϕϕ2−ϕ1\phi\phi_2-\phi_1ϕϕ2​−ϕ1​。 根据磁矢势A的定义&#xff0c;B…...

什么是L1和L2正则化,以及它们有什么区别

一、L1和L2正则化是什么&#xff1f; 在防止过拟合的方法中有L1正则化和L2正则化&#xff0c;L1和L2是正则化项&#xff0c;又叫做惩罚项&#xff0c;是为了限制模型的参数&#xff0c;防止模型过拟合而加在损失函数后面的一项。 在二维的情况下&#xff0c;黄色的部分是L2和…...

场景式消费激发春日经济,这些电商品类迎来消费热潮

春日越临近&#xff0c;商机越浓郁。随着气温渐升&#xff0c;春日经济已经潜伏在大众身边。“春菜”、“春装”、“春游”、“春季养生”等春日场景式消费走热。 下面&#xff0c;鲸参谋为大家盘点几个与春日经济紧密相关的行业。 •春日仪式之春游踏青 ——户外装备全面开花…...

[2.1.4]进程管理——进程通信

文章目录第二章 进程管理进程通信&#xff08;IPC&#xff09;为什么进程通信需要操作系统支持&#xff1f;&#xff08;一&#xff09;共享存储&#xff08;1&#xff09;基于存储区的共享&#xff08;2&#xff09;基于数据结构的共享&#xff08;二&#xff09;消息传递什么…...

ChatGPT也有犯晕的时候

前面测试 ChatGPT 进行写代码、优化代码、解释代码、一般问答都表现的很好。偷个懒&#xff0c;用ChatGPT 帮我写段生物信息代码如果 ChatGPT 给出的的代码不太完善&#xff0c;如何请他一步步改好&#xff1f;代码看不懂&#xff1f;ChatGPT 帮你解释&#xff0c;详细到爆&…...

机器学习与目标检测作业:连通块算法

机器学习与目标检测作业&#xff1a;连通块算法一、连通块算法题目描述二、连通块算法文件结构三、连通块算法程序编写3.1、连通块算法conBlock.h头文件内容3.2、conBlock.cpp源文件内容3.3.3、mian.h头文件内容3.3.4、main.cpp源文件内容如下四、连通块算法程序运行结果一、连…...

HBase基础 --- 增删查改

目录 创建表 查看指定表全名空间中的表 查看表描述 禁用/启用 查看禁用/启动状态 删除表 新增列族 删除列族 更改列族存储版本的限制 增加数据 根据条件查询 查看指定列中不同版本的数据 删除指定列族下的指定列 删除指定行 全表扫描 全表扫描指定列族…...

如何基于AI智能视频技术实现公园景区的人流量实时统计?

一、方案背景春暖花开的季节来临&#xff0c;外出旅游的人群也越来越多。无论是景区、公园、博物馆、步行街等场所&#xff0c;客流超载非常大&#xff0c;给游客带来的体验较差&#xff0c;同时也存在安全隐患。当前景区面临的管理痛点包括&#xff1a;客流信息查询难&#xf…...

【JavaWeb】Servlet详解

文章目录1. 前置知识2.servlet生命周期2.1 默认情况下&#xff0c;服务器启动时&#xff0c;servlet对象并没有被创建2.2 用户执行一次请求2.3用户执行第二次请求2.4 3,4,5,6....次请求2.5 关闭服务器3.servlet方法解析4.适配器模式改造servlet4.1不使用servlet模式4.2使用适配…...

谁是世界上最好的编程语言?--编程语言70年浅谈

1、编程语言发展史纵览 严谨起见&#xff0c;本文提到的编程语言指的是「第三代高级编程语言」。 首先&#xff0c;我们从时间维度入手聊聊编程语言。一图胜千言&#xff0c;我们从目前主流的编程语言中&#xff0c;挑选出流行的、具有历史影响力的语言。把它们按时间从上往下…...

Webpack前端资源加载/打包工具

文章目录一、Webpack1、什么是Webpack2、Webpack安装2.1全局安装2.2安装后查看版本号3、创建项目3.1初始化项目3.2创建src文件夹3.3 src下创建common.js3.4 src下创建utils.js3.5 src下创建main.js4、JS打包4.1创建配置文件4.2执行编译命令4.3创建入口页面4.4测试5、CSS打包5.1…...

springcloud3 fegin实现服务调用1

一 Fegin的作用 1.1 fegin的作用 fegin是一个声明式的web服务客户端&#xff0c;让编写web服务器客户端变得非常容易&#xff0c;只需创建一个接口并在接口中添加FeginClients注解即可。 Fegin的使用方式&#xff1a;使用fegin的注解定义接口&#xff0c;调用这个接口&#…...

专业版即将支持自定义场景测试

物联网 MQTT 测试云服务 XMeter Cloud 专业版于 2022 年底上线后&#xff0c;已有不少用户试用&#xff0c;对数千甚至上万规模的 MQTT 并发连接和消息吞吐场景进行测试。同时我们也收到了希望支持更多物联网协议测试的需求反馈。 新年伊始&#xff0c;XMeter 团队全力聚焦于 …...

Process Monitor工具使用实验(23)

实验目的 学习Process Monitor实用小工具的使用&#xff0c;学会利用Process Monitor工具观察程序进程/线程、文件系统、注册表、网络连接等的活动。预备知识 Process Monitor是一个Windows系统下先进的监视工具&#xff0c;它可以显示文件系统、注册表、网络连接、进程…...

钓鱼客服到拿下服务器全过程(重点在于钓鱼添加img src)

重点总结 钓鱼时主动在变量中添加了字段&#xff0c;等待用户点击获取ip信息进行下一步资金盘plus呢 左看右看没啥东西&#xff0c;看看客服系统能不能打xss。 吊毛客服居然不在线&#xff0c;这套客服系统见过是whisper&#xff0c;之前审计过没有存储xss 但能通过伪造图片…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...