【C++差分数组】P1672何时运输的饲料
本文涉及知识点
C++差分数组
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
P1672何时运输的饲料
原文比较啰嗦,我简述一下:
第x天运来F1(1<=F1<=1e6)千克的饲料,第D(1<=2e3)天还剩F2(1 <= F2 <= F1)千克饲料,某人养了C头牛,moves[i] = {comi,leavei},表示第i头牛第comi天来,第leavei天离开,牛每天都要吃1千克的饲料,包括来和离开的那天。第x天运输饲料之前,饲料刚好光了,且当天的牛都是吃运来的饲料。第D天吃过饲料了。
求最大X。
差分数组
本题 ⟺ \iff ⟺ 牛第x到D吃的饲料等于F2-F1。
令牛从0到d天共吃了y。则第x到D吃的饲料等于y - 第0到x-1吃的饲料。
差分数组diff[i]记录第i天牛的增加,对应的数据数组a 记录第i天牛的数量。
a的前缀和preSum就是前i天牛吃的饲料。
注意:第D天之后离开的当成第D天离开,否则吃的饲料会计算错误。
也可以不用前缀和,直接枚举从D到0枚举i计算资料消耗量,如果等于f1-f2,则返回i。
代码
打开打包代码的方法兼述单元测试
不用前缀和
#include <iostream>#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;class Solution {
public:int Cal(int f1,int f2, int d,const vector<vector<int>>& moves) {const int N = min(2'000, d);vector<int> diff(N + 2);for (const auto& v : moves) {diff[v[0]]++;diff[min(v[1],d) + 1]--;} vector<int> a(N + 2);int cnt = 0;for (int i = 0; i < diff.size(); i++) {cnt += diff[i];a[i] = cnt;}int use = 0;for (int i = d; i >= 0; i--) {use += a[i];if (f1 - f2 == use) { return i; }}return -1;}
};int main() {int c, f1, f2, d;scanf("%d%d%d%d", &c, &f1, &f2, &d);vector<vector<int>> moves(c, vector<int>(2)); for (int i = 0; i < c; i++) {scanf("%d%d", &moves[i][0], &moves[i][1]);}cout << Solution().Cal(f1, f2, d, moves);return 0;
}
单元测试
int f1, f2, d;vector<vector<int>> moves;TEST_METHOD(TestMethod1){f1 = 14, f2 = 14, d = 10;moves = { };auto res = Solution().Cal(f1, f2, d, moves);AssertEx(10, res);}TEST_METHOD(TestMethod2){f1 = 14, f2 = 10, d = 10;moves = { {1,4} };auto res = Solution().Cal(f1, f2, d, moves);AssertEx(1, res);}TEST_METHOD(TestMethod11){f1=14, f2=4, d=10;moves = { {1,9},{5,8},{8,12} };auto res = Solution().Cal(f1, f2, d, moves);AssertEx(6, res);}

扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
| 学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
| 有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【C++差分数组】P1672何时运输的饲料
本文涉及知识点 C差分数组 C算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 P1672何时运输的饲料 原文比较啰嗦,我简述一下: 第x天运来F1(1<F1<1e6)千克的饲料,第D(1<2e3)天还剩F2&…...
Go基础知识:切片
数组 Go 数组的大小是固定的,其长度是其类型的一部分([4]int并且[5]int是不同的、不兼容的类型) var a [10]intb : [2]string{"Penn", "Teller"} b : [...]string{"Penn", "Teller"}package maini…...
Redis配置篇 - 指定Redis配置的三种方式,以及Redis配置文件介绍
文章目录 1 指定Redis配置的三种方式1.1 通过命令行参数来指定Redis配置1.2 通过配置文件来指定Redis配置1.3 在服务器运行时更改 Redis 配置 2 关于Redis配置文件 1 指定Redis配置的三种方式 1.1 通过命令行参数来指定Redis配置 在redis启动时,可以直接通过命…...
探索scikit-learn的datasets模块:数据集的加载与使用
引言 在机器学习和数据分析领域,数据集的选择和准备是至关重要的一步。scikit-learn库的datasets模块为我们提供了多种内置的数据集,方便我们进行模型训练和测试。这些数据集既有大型的数据集,也有便于教学和初步探索的小型数据集。本文将重…...
手机使用技巧:8 个 Android 锁屏移除工具 [解锁 Android]
有时候,您会被锁定在自己的 Android 设备之外,而且似乎不可能重新进入。 一个例子就是你买了一部二手手机,后来发现无法使用。另一种情况是你忘记了屏幕锁定密码和用于验证密码的 Google 帐户凭据。这种情况很少见,但确实会发生&…...
SSL 协议(HTTPS 协议的关键)
所谓的协议 协议只是一种规则,你不按规则来就无法和目标方进行你的工作 协议说白了只是人定的规则,任何人都可以定协议 我们不需要太了解细节,这些是制定和完善协议的人去做的,我们只需要知道协议的一个大概 一、SSL 协议 1、…...
test_2_27(C指针)
test_2_27 #define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>使用指针数组来模拟实现二维数组int main() {int* arr[10];//指针数组int arr1[] { 1,2,3,4,5 };int arr2[] { 2,3,4,5,6 };int arr3[] { 3,4,5,6,7 };int* arr[3] {arr1, arr2, arr3};int i 0;for …...
设计模式——门面模式 | 外观模式
哈喽,各位盆友们!我是你们亲爱的学徒小z,今天给大家分享的文章是设计模式的——门面模式。 文章目录 定义通用类图1.通用结构2.优点3.缺点 使用场景注意事项1.一个子系统可以有多个门面2.门面不参与子系统内的业务逻辑 定义 定义:…...
FPGA时序分析和约束学习笔记(1、FPGA基本原理)
FPGA时序分析和约束学习笔记-(1、FPGA基本原理) Field现场Programmable可编程Gate门Array阵列 1、FPGA基本资源组成 可编程逻辑功能块(logic elements ,缩写LE) 片内互联线(interconnect,缩写…...
VMware桥接模式无法连接网络
windows下打开控制面板,找到WLAN,记住下面的名称(带有VMware的都是虚拟机的网卡,要找到物理主机的网卡) 回到VMware,编辑——打开虚拟网络编辑器 桥接选择上面的WLAN下的网络名称,确定即可。&…...
YOLO11改进|卷积篇|引入空间通道重组卷积ScConv
目录 一、【SCConv】卷积1.1【SCConv】卷积介绍1.2【SCConv】核心代码 二、添加【SCConv】卷积2.1STEP12.2STEP22.3STEP32.4STEP4 三、yaml文件与运行3.1yaml文件3.2运行成功截图 一、【SCConv】卷积 1.1【SCConv】卷积介绍 SCConv 模块提供了一种新的视角来看待CNNs的特征提取…...
Java:方法详解
目录 一.什么是方法(method) 二.方法定义 三.方法中实参和形参的关系 四.方法重载 五.递归 一.什么是方法(method) 方法就是一个代码片段,再C语言中我们曾经学过一个类似的方式——函数,他们都是将具有独立功能的代码组织成一个整体,形成…...
Python 三方库下载安装
Python 三方库下载安装 1、在线安装 pip install pandas # 直接安装 python -m pip install pandas # 使用指定Python中的pip进行安装 pip install pandas1.2.3 # 安装指定版本 pip install pandas -i http://pypi.douban.com/simple --trusted-host pypi.…...
使用npm i报错node-sass失败问题解决
node 版本:v14.15.4 解决方法: npm config set sass_binary_sitehttps://npmmirror.com/mirrors/node-sass设置完之后,再npm i 就可以下载成功 亲测有效...
vite+vue3实现动态路径导入
最近在做一个项目有个需求: 项目图片分为英语,中文,德语 ,我将这些图片存放到/image/language/下面的每个语言的文件夹内,如en,zh-cn文件夹下面存放对应的语言的图片,如果在代码里面写路径的话,除了要写一堆路径还要判断不同的语言,非常麻烦,但是在vue3vite里面import导入的是加…...
JAVA——File类
目录 1.概述 2.构造方法 a.根据文件路径创建文件对象 b.根据父级路径和子级路径创建对象 c.根据File表示的路径和String表示路径进行拼接 3.常见方法 a.判断文件是否存在 b.判断文件是否为文件夹 c.判断是否为文件 d.获取文件大小 e.获取文件的绝对路径 f.获取定义…...
掌握Postman,开启API测试新纪元!
Postman是一款流行的API测试工具和开发环境,旨在简化API开发过程、测试和文档编制。它提供了一套功能强大的工具,帮助开发人员更轻松地构建、测试和调试Web服务。 Postman 工具的优势 Postman 可以快速构建请求、还可以保存以后再使用。 Postman 还提…...
JAVA-数据结构-排序
1.直接插入排序 1.原理:和玩扑克牌一样,从左边第二个牌开始,选中这个,和前面的所有牌比较,插在合适的位置 public static void insertsort(int[] arr){//直接插入排序for (int i 1; i < arr.length; i) {//此循环…...
初识数据结构--时间复杂度 和 空间复杂度
数据结构前言 数据结构 数据结构是计算机存储、组织数据的方式(指不仅能存储数据,还能够管理数据-->增删改)。指相互之间存在一种或多种特定关系的数据元素的集合。没有单一的数据结构对所有用途都有用,所以我们要学习各种的数据结构,比…...
Ubuntu QT 交叉编译环境搭建
文章目录 下载安装qtCreatornot a valid identifier 的错误 安装g下载并安装交叉编译器下载交叉编译器安装交叉编译器 下载编译 ARM 的Qt平台源码配置arm的QT平台 下载安装qtCreator 去QT下载官网下载对应需要的QT软件。 这里下载5.12.96版本的 改变安装包权限,…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
