【C++差分数组】P1672何时运输的饲料

CSDN 2024-10-20 13:35:01 阅读 51

本文涉及知识点

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。

代码

打开打包代码的方法兼述单元测试

不用前缀和

<code>

#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++**实现。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。