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

【C++差分数组】P10903 商品库存管理

news 2024/10/25 7:30:21

本文涉及知识

C++差分数组

洛谷 P10903 商品库存管理

题目简述：
有n中商品，编号[1,n]。有m中操作 ope[i]={LI,RI}，将编号LI到LR的商品都加1。
有m个查询，第i个查询，执行所有ope[i],i $\neq$ i 后为0的商品数。
1 <=n,m <= 3e5 1 <=LI,RI <= n

差分数组

差分数组diff，这些所有ope ，即diff[LI]++ ,diff[RI+1]–。对应的数据数组a，就是各商品的数量。
如果某个商品的数量为0,则任何查询都为0，记作cnt0。
如果某个商品的数量>=2，则任何查询都大于0，一定不符合条件。
只需要记录商品数量为1的编号。二分查找在[LI,RI]的数量cnt1。
结果就是cnt0+cnt1。

代码

class Solution {
public:vector<int> Cal(const int N, vector<vector<int>>& ope) {vector<int> diff(N+2);for (const auto& v : ope) {diff[v[0]]++;diff[v[1] + 1]--;}vector<int> ones;int cnt0 = 0;int cur = 0;for (int i = 1; i <= N; i++) {cur += diff[i];cnt0 += (0 == cur);if (1 == cur) {ones.emplace_back(i);}}vector<int> ret;for (const auto& v : ope) {auto it1 = lower_bound(ones.begin(), ones.end(), v[0]);auto it2 = upper_bound(ones.begin(), ones.end(), v[1]);ret.emplace_back(cnt0 + (it2 - it1));}return ret;}
};int main() {//freopen("./a.in", "r", stdin);//freopen("./output.txt", "a", stdout);int n,m;scanf("%d%d", &n, &m);vector<vector<int>> ope(m,vector<int>(2));	for (int i = 0; i < m; i++) {scanf("%d%d", &ope[i][0],&ope[i][1]);}	auto res = Solution().Cal(n,ope);for (auto& n : res) {printf("%d\n", n);}return 0;
}

单元测试

int N;vector<vector<int>> ope;TEST_METHOD(TestMethod1){N = 3, ope = { {1,1} };auto res = Solution().Cal(N, ope);AssertEx(vector<int>{3}, res);}TEST_METHOD(TestMethod2){N = 3, ope = { {1,1},{2,3} };auto res = Solution().Cal(N, ope);AssertEx(vector<int>{1, 2}, res);}TEST_METHOD(TestMethod3){N = 3, ope = { {1,1},{1,3} };auto res = Solution().Cal(N, ope);AssertEx(vector<int>{0, 2}, res);}TEST_METHOD(TestMethod11){N = 5, ope={ {1, 2}, { 2,4 }, { 3,5 } };auto res = Solution().Cal(N,ope);AssertEx(vector<int>{1, 0, 1}, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功