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

本文涉及知识

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);
		}

扩展阅读

视频课程

先学简单的课程，请移步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++**实现。