当前位置: 首页 > 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;并进行验证。 示例代…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

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

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

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

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

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

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...