当前位置: 首页 > 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 但能通过伪造图片…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...

【技巧】dify前端源代码修改第一弹-增加tab页

回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码&#xff0c;在知识库增加一个tab页"HELLO WORLD"&#xff0c;完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...

Java设计模式:责任链模式

一、什么是责任链模式&#xff1f; 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09; 是一种 行为型设计模式&#xff0c;它通过将请求沿着一条处理链传递&#xff0c;直到某个对象处理它为止。这种模式的核心思想是 解耦请求的发送者和接收者&#xff0c;…...

MySQL基本操作(续)

第3章&#xff1a;MySQL基本操作&#xff08;续&#xff09; 3.3 表操作 表是关系型数据库中存储数据的基本结构&#xff0c;由行和列组成。在MySQL中&#xff0c;表操作包括创建表、查看表结构、修改表和删除表等。本节将详细介绍这些操作。 3.3.1 创建表 在MySQL中&#…...