【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版本的 改变安装包权限,…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
