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

C语言巨难题:执行操作可获得的最大总奖励 I(C语言版)

1.题目:

给你一个整数数组 rewardValues,长度为 n,代表奖励的值。

最初,你的总奖励 x 为 0,所有下标都是 未标记 的。你可以执行以下操作 任意次 

  • 从区间 [0, n - 1] 中选择一个 未标记 的下标 i
  • 如果 rewardValues[i] 大于 你当前的总奖励 x,则将 rewardValues[i] 加到 x 上(即 x = x + rewardValues[i]),并 标记 下标 i

以整数形式返回执行最优操作能够获得的 最大 总奖励。

示例 1:

输入:rewardValues = [1,1,3,3]

输出:4

解释:

依次标记下标 0 和 2,总奖励为 4,这是可获得的最大值。

示例 2:

输入:rewardValues = [1,6,4,3,2]

输出:11

解释:

依次标记下标 0、2 和 1。总奖励为 11,这是可获得的最大值。

提示:

  • 1 <= rewardValues.length <= 5 * 104
  • 1 <= rewardValues[i] <= 5 * 104

该作者解决方法:

不知道C语言要怎么建构bitset,看了其他人的解答后尝试用位运速加速。 假设有一个 bool 数组 dp。在每一次循环中,dp[rewardValues[i] + j] 可以由 dp[j] 转移而来,其中 j 为小于 rewardValues[i] 的非负整数。 为了加速运算并减少空间浪费,可以将 bool 数组改成 unsigned long long。 在C语言中,虽 bool 使用1bit,但最小寻址单位为1字节,所以占用1字节。 现在我们将数组声明成 unsigned long long,此时每次操作最多可以操作64个位元,也就是64个状态。 由于 rewardValues[i] 不一定为64的倍数,为了避免发生溢位的状况,必须将 dp[j] 所代表的64位元拆成两部分。 为了计算正确的下标,我们把 rewardValues[i] 用 index 与 digit 表示,其中 rewardValues[i] = 64 * index + digit:
index = rewardValues[i] / 64
digit = rewardValues[i] % 64
因此,对于每个下标 j,dp[j] 可拆成:
(dp[j] & ((1 << (64 - digit)) - 1)) << digit
dp[j] >> (64 - digit)
假设 rewardValues[i] = 65,那么:
index = 65 / 64 = 1
digit = 65 % 64 = 1
以 dp[0] 的 0 ~ 63 位为例,0 ~ 62 位可以移到 dp[index + 0] 中的 1 ~ 63 位,对应数字 65 ~ 127。而剩下的1个位则放入 dp[index + 1] 的第 0 位,这个过程通过或运算即可。
dp[index + j] |= (dp[j] & ((1 << (64 - digit)) - 1)) << digit;
dp[index + j + 1] |= dp[j] >> (64 - digit);
若 rewardValues[i] 为 64 的倍数可直接转移,不需拆分

代码:

int cmp(const void *a, const void *b)
{return *(int*)a > *(int*)b;
}int maxTotalReward(int* rewardValues, int rewardValuesSize)
{qsort(rewardValues, rewardValuesSize, sizeof(int), cmp);int size = rewardValues[rewardValuesSize - 1] / 32 + 2;unsigned long long dp[size], temp, mask;memset(dp, 0, sizeof(unsigned long long) * size);int index, digit;dp[0] = 1;for (int i = 0; i < rewardValuesSize; ++i) {index = rewardValues[i] / 64;digit = rewardValues[i] % 64;mask = digit ? (1ULL << (64 - digit)) - 1 : 0;for (int j = 0; j < index; ++j){if (digit) {dp[j + index] |= (dp[j] & mask) << digit;dp[j + index + 1] |= dp[j] >> (64 - digit);} else {dp[j + index] |= dp[j];}}if (digit) {temp = dp[index] & ((1ULL << digit) - 1);dp[2 * index] |= (temp & mask) << digit;dp[2 * index + 1] |= temp >> 64 - digit;}}for (int i = size - 1; i >= 0; --i) {if (dp[i])return 64 * i + 63 - __builtin_clzll(dp[i]);}return 0;
}

声明:来源力扣题解

作者:borane

链接:https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/solutions/2805771/01bei-bao-wei-yun-suan-by-modest-nashdn2-svmq/

来源:力扣(LeetCode)

相关文章:

C语言巨难题:执行操作可获得的最大总奖励 I(C语言版)

1.题目&#xff1a; 给你一个整数数组 rewardValues&#xff0c;长度为 n&#xff0c;代表奖励的值。 最初&#xff0c;你的总奖励 x 为 0&#xff0c;所有下标都是 未标记 的。你可以执行以下操作 任意次 &#xff1a; 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。如果…...

【力扣】GO解决子序列相关问题

文章目录 一、引言二、动态规划方法论深度提炼子序列问题的通用解法模式 三、通用方法论应用示例&#xff1a;最长递增子序列&#xff08;LeetCode题目300&#xff09;Go 语言代码实现 四、最长连续递增序列&#xff08;LeetCode题目674&#xff09;Go 语言代码实现 五、最长重…...

Ubuntu20.04安装VM tools并实现主机和虚拟机之间文件夹共享

1、Ubuntu20.04安装VM tools 参考这个&#xff0c;很详细&#xff1a;Ubuntu 20.04 安装 VMwareTools 教程 2、实现主机与VMware虚拟机共享文件夹 设置共享文件夹参考&#xff1a;windows和虚拟机互传文件的三种方式 挂载操作参考&#xff1a;主机与VMware虚拟机共享文件夹&…...

Linux 学习笔记(十七)—— 文件系统

终极目标&#xff1a;理解 inode 和 软硬连接&#xff1b; 文件系统&#xff1a;Ext2; 文件 文件内容 文件属性; ——> 磁盘上存储的文件 存储的文件内容 存储的文件属性&#xff1b; Linux系统中&#xff1a;文件内容使用数据块存储&#xff0c;文件属性使用inode(固定…...

【计算机网络 - 基础问题】每日 3 题(五十八)

✍个人博客&#xff1a;https://blog.csdn.net/Newin2020?typeblog &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞…...

Netty入门基础:IO模型中BIO\NIO概念及区别【附演示代码】

文章目录 &#x1f600;BIO&#x1f4a2;实战demo &#x1f308;NIO&#x1f3cd;Buffer核心属性核心方法 &#x1f397;Channel&#x1f388;Selector核心方法 &#x1f9e8;实战demo &#x1f3a8;粘包与半包 &#x1f600;BIO 传统IO模型&#xff0c;同步阻塞&#xff0c;每…...

vue2 使用环境变量

一. 在根目录下创建.env.xxx文件 .env 基础系统变量&#xff0c;无论何种环境&#xff0c;都可使用其中配置的值&#xff0c;其他环境中的变量会覆盖.env中的同名变量。 .env.development 开发环境 .env.production 生产环境 .env.staging 测试环境 二. 内容格式 vue2 使用是以…...

数据预处理

继续提取代码片段&#xff1a; 12. **导入iris数据集并查看前5行数据**&#xff1a; python from sklearn.datasets import load_iris iris load_iris() X iris.data print(iris数据集的维度为:, X.shape) print(iris数据集的前5行数据为:\n, X[:5]) …...

django宠物领养管理系统-计算机毕业设计源码26858

目录 1 绪论 1.1 选题背景与意义 1.2国内外研究现状 1.3论文结构与章节安排 2系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.5本章小结 3 系统总体设计 3…...

使用TeamViewer远程局域网内的两台电脑

有个场景&#xff0c;有人还不知道TV可以局域网操作&#xff0c;记录一下。 主要就是修改设置&#xff0c;将取消激活改为接受 然后输入受控端的ip即可...

GUI简介、Swing的常用组件、java程序的运行过程、class文件、JAR、runable_jar、双括号初始化

GUI简介 GUI&#xff1a;图形用户界面&#xff0c;在计算机中采用图形的方式显示用户界面 java的GUI开发 AWT&#xff1a;java最早推出的GUI编程开发包&#xff0c;界面风格跟随操作系统SWT&#xff1a;eclipse就是java使用SWT开发的Swing&#xff1a;在AWT的基础上扩充了功能…...

@Autowired和@Resource和getBean()区别

今天遇到一个对我来说很奇葩的错误&#xff0c;我想在Service中注入bean&#xff0c;我这里使用了Autowired和Resource都不能注入&#xff0c;导致初始化失败&#xff0c;使用了getBean()方法就可以注入。从来没有遇到过这个问题。后来我查询了一下&#xff0c;才明白了原理。我…...

Merlion笔记(四):添加一个新的预测模型

文章目录 1 模型配置类2 模型类3 运行模型&#xff1a;一个简单的例子4 可视化5 定量评估6 定义一个基于预测器的异常检测器 本文提供了一个示例&#xff0c;展示如何向 Merlion 添加一个新的预测模型,遵循 CONTRIBUTING.md 中的说明。建议在阅读本篇文章之前&#xff0c;先查…...

【论文阅读】ESRGAN

学习资料 论文题目&#xff1a;增强型超分辨率生成对抗网络&#xff08;ESRGAN: Enhanced Super-Resolution Generative Adversarial Networks&#xff09;论文地址&#xff1a;[1809.00219] ESRGAN&#xff1a;增强型超分辨率生成对抗网络代码&#xff1a;xinntao / ESRGAN&am…...

电脑异常情况总结

文章目录 笔记本无症状息屏黑屏 笔记本无症状息屏黑屏 &#x1f34e; 问题描述&#xff1a; 息屏导致黑屏&#xff1b;依次操作计算机--》右键--》管理--》事件查看器--》Windows日志--》系统&#xff1b;从息屏到异常黑屏之间出现了很多错误&#xff0c;如下&#xff1a;事件…...

[项目详解][boost搜索引擎#1] 概述 | 去标签 | 数据清洗 | scp

目录 一、前言 二、项目的相关背景 三、搜索引擎的宏观原理 四、搜索引擎技术栈和项目环境 五、正排索引 VS 倒排索引--原理 正排索引 分词 倒排索引 六、编写数据去除标签和数据清洗模块 Parser 1.数据准备 parser 编码 1.枚举文件 EnumFile 2.去标签ParseHtml(…...

PL/I语言的起源?有C语言,有B语言和A语言吗?为什么shell脚本最开始可能有#!/bin/bash字样?为什么不支持嵌套注释?

PL/I语言的起源 在20世纪50~60年代&#xff0c;当时主流的编程语言是COBOL/FORTRAN/ALGOL等&#xff0c;IBM想要设计一门通用的编程语言&#xff0c;已有的编程语言无法实现此要求&#xff0c;故想要设计一门新语言&#xff0c;即是PL/I. PL/I是Programming Language/One的缩写…...

gin入门教程(3):创建第一个 HTTP 服务器

首先设置golang github代理&#xff0c;可解决拉取git包的时候&#xff0c;无法拉取的问题&#xff1a; export GOPROXYhttps://goproxy.io再查看自己的go版本&#xff1a; go version我这里的版本是&#xff1a;go1.23.2 linux/arm64 准备工作做好之后就可以进行开发了 3.…...

Vue+ECharts+iView实现大数据可视化大屏模板

Vue数据可视化 三个大屏模板 样式还是比较全的 包括世界地图、中国地图、canvas转盘等 项目演示&#xff1a; 视频&#xff1a; vue大数据可视化大屏模板...

el-table 表格设置必填项

el-table 表格设置必填项 要在 el-table 中集成 el-form 来设置必填项&#xff0c;并进行表单验证&#xff0c;可以使用 Element UI 提供的表单验证功能。下面是一个详细的示例&#xff0c;展示了如何在 el-table 中使用 el-form 来设置必填项&#xff0c;并进行验证。 示例代…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...