本文涉及知识点

C++贪心
C++差分数组

[CCO2022] Rainy Markets

题目背景

由于数据包过大，本题无法上传全部数据。

题目描述

有 $N$ 个公交车站，标号为 $1,\dots ,N$。第 $i$ 个公交车站可以容纳 $B_i$ 个人。

对于每个 i ∈ { 1 , … , N − 1 } i \in\{1, \ldots, N-1\} i∈{1,…,N−1}，有一条人行道连接公交车站 $i$ 和公交车站 $i+1$，中间有一个露天市场。第 $i$ 个市场有 $U_i$ 把雨伞出售，每把雨伞的价格为 $$ 1$。

现在，有 $P_i$ 个人在第 $i$ 个市场里面，所有的公交车站都是空的。

突然，天开始下雨，市场 $i$ 的每个人都必须在三种方案中选择一种：

• 去公交车站 $i$；
• 去公交车站 $i+1$；
• 留下来买一把雨伞。

如果一个人无法在某个公交车站下或者买一把雨伞，他们就会淋湿。

你需要回答如果在最优的安排方案下，能否确保每个人都能不被雨淋湿。如果是的话，你需要给出他们需要花费的最少的钱，以及每个人应该移动到哪个公交车站。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个用空格分隔的整数 $B_i(1\le i\le N)$，表示公交车站 $i$ 的容量。

第三行包含 $N-1$ 个用空格分隔的整数 $P_i(1\le i\le N-1)$，表示市场 $i$ 的人数。

第四行包含 $N-1$ 个用空格分隔的整数 $U_i(1\le i\le N-1)$，表示市场 $i$ 出售的雨伞的数量。

输出格式

如果每个人都能在雨伞或公交车站下，输出 $N+1$ 行：

• 第一行输出一行 YES。
• 第二行输出一个整数，表示包含在雨伞上花费的最少的钱。
• 接下来的 $N-1$ 行，每行输出三个用空格分隔的整数分别表示市场 $i(1\le i\le N-1)$ 移动到公交车站 $i$ 的人数，市场 $i$ 买雨伞的人数，市场 $i$ 移动到公交车站 $i+1$ 的人数。

如果有多种合法方案，你可以输出任意一种。

否则，输出一行 NO。

样例 #1

样例输入 #1

3
10 15 10
20 20
0 0

样例输出 #1

NO

样例 #2

样例输入 #2

3
10 15 10
20 20
0 11

样例输出 #2

YES
5
10 0 10
5 5 10

提示

样例 1 解释

公交车站有 $35$ 个空位，没有雨伞出售，但市场有 $40$ 个人，所以答案是 NO。

样例 2 解释

市场 $1$ 中的 $10$ 个人会去公交车站 $1$，没有人会买雨伞，$10$ 个人会去公交车站 $2$。

市场 $2$ 中的 $5$ 个人会去公交车站 $2$，$5$ 个人会留下来买雨伞，$10$ 个人会移动到公交车站 $3$。

总共购买了 $5$ 把雨伞，花费了 $$ 5$。

数据范围

对于所有的数据，有 $2\le N\le 10^6$，$0\le B_i\le 2\cdot 10^9$，$0\le P_i,U_i\le 10^9$。

子任务编号	分值	$N$	$B$	$P$	$U$
$1$	$20$	$2\le N\le 10^6$	$0 \leq B_{i} \leq 2 \cdot 10^{9} $	$0\le P_i\le 10^9$	$U_i=0$
$2$	$20$	$2\le N\le 2000$	$0\le B_i\le 400$	$ 0 \leq P_{i} \leq 200$	$0\le U_i\le 200$
$3$	$24$	$2\le N\le 4000$	$0\le B_i\le 4000$	$0\le P_i\le 2000$	$0\le U_i\le 2000$
$4$	$36$	$2\le N\le 10^6$	$0\le B_i\le 2\cdot 10^9$	$0\le P_i\le 10^9$	$0\le U_i\le 10^9$

反悔贪心 懒惰堆 差分数组

市场的人，先向左走，满了后，右走。最后买伞。优先买市场编号最小的伞。如果市场伞不够，则返回失败。

j < i，市场i的人从市场j买雨伞（反悔）的条件：
市场j有雨伞，市场[j…i-1]现存右移数大于0。
结果：
市场j雨伞-1。
市场[j…i-1]右移-1。
市场[j+1…i]左移+1。
注意： i 等于 j的时候也成立。
左移右移的变化用差分数组记录。
判断市场[j…i-1]是否存在右移，用小根堆。小根堆记录 {x1=右移动数量+已买雨伞数量has，市场编号x2}。入堆后，每买一把雨伞，右移动数量减1,等效果于 已买雨伞加加。
队列记录：{剩余雨伞数，市场编号}

当 P[i] > 0 执行买伞
当队列首雨伞数 <=0 出队
队列为空，无法购买，返回空。
当堆顶的市场编号小于队首市场编号，出堆。懒删除堆
如果堆为空,m1 = P[i] ，否则 m1 = 堆顶移动数
cur = min(m1,P[i],队首雨伞数)
has += cur
P[i] -= cur
队首元素雨伞数 -= cur
记录买伞、左移、右移变化数。
如果栈顶元素x1 <= has，当队首元素的市场编号 <= x2，则出队。 出栈。

增加当前市场的雨伞，在执行买伞之前。增加当前的右移数量，在执行买伞之后；如果右移数量为0，可能要清理队头。

代码

核心

100多个样例，有一个略略超时。

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>

#include <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret;
	T d ;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}
class CStatu
{
public:
	CStatu(int N) :m_buy(N - 1), m_diffR(N), m_diffL(N) {

	}
	void AddU(int i, int u) {
		m_que.emplace(u, i);
	}
	void AddRightMove(int i, long long move) {
		m_heap.emplace(move + m_llHasBuy, i);
		EraseQueueFront();
	}
	bool Buy(int i, int iNeedBuy) {
		while (iNeedBuy > 0) {
			while (m_que.size() && (m_que.front().first <= 0)) { m_que.pop(); }
			if (m_que.empty()) { return false; }
			while (m_que.size() && m_heap.size() && (m_heap.top().second < m_que.front().second)) {
				m_heap.pop();
			}
			const int m1 = m_heap.empty() ? iNeedBuy : (m_heap.top().first - m_llHasBuy);
			int cur = min(m1, iNeedBuy);
			cur = min(cur, m_que.front().first);
			m_llHasBuy += cur;
			iNeedBuy -= cur;
			m_que.front().first -= cur;
			Record(i, cur);
			EraseQueueFront();
		}
		return true;
	}
	void Record(int i, int cur) {
		m_buy[m_que.front().second] += cur;
		m_diffR[m_que.front().second] -= cur;
		m_diffR[i] += cur;
		m_diffL[m_que.front().second + 1] += cur;
		m_diffL[i + 1] -= cur;
	}
	void EraseQueueFront() {
		if (m_heap.empty() || (m_heap.top().first > m_llHasBuy)) { return; }
		while (m_que.size() && (m_que.front().second <= m_heap.top().second)) {
			m_que.pop();
		}
		m_heap.pop();
	}
	vector<int> m_buy;
	vector<long long> m_diffR, m_diffL;
	long long m_llHasBuy = 0;
	queue<pair<int, int>> m_que;
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> m_heap;
};
class Solution {
public:
	vector<tuple<int, int, int>> Do(long long& llBuy, vector<int>& B, vector<int>& P, vector<int>& U)
	{
		const int N = B.size();
		CStatu stu(N);
		vector<int> left(N - 1), right(N - 1);//left[i]第i个市场，左移的人数			
		for (int i = 0; i + 1 < N; i++) {
			const int iPreRight = (0 == i ? 0 : right[i - 1]);
			left[i] = min(B[i] - iPreRight, P[i]);
			P[i] -= left[i];
			right[i] = min(P[i], B[i + 1]);
			P[i] -= right[i];
			stu.AddU(i, U[i]);
			if (!stu.Buy(i, P[i])) { return {}; }
			stu.AddRightMove(i, right[i]);
		}
		long long llL = 0, llR = 0;
		vector<tuple<int, int, int>> ans;
		for (int i = 0; i + 1 < N; i++) {
			llL += stu.m_diffL[i];
			llR += stu.m_diffR[i];
			left[i] += llL;
			right[i] += llR;
			ans.emplace_back(left[i], stu.m_buy[i], right[i]);
		}
		llBuy = stu.m_llHasBuy;
		return ans;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int n;
	scanf("%d", &n);
	auto B = Read<int>(n);
	auto P = Read<int>(n - 1);
	auto U = Read<int>(n - 1);
	long long llBuy = 0;
	auto res = Solution().Do(llBuy,B, P, U);
	if (0 == res.size()) { cout << "NO\r\n"; }
	else {
		cout <<"YES" << std::endl << llBuy << std::endl;
		for (const auto& [i1, i2, ll] : res) {
			cout << i1 << " " << " " << i2 << " " << ll << std::endl;
		}		
	}
	return 0;
}

单元测试

	void Check(const vector<int>& B, const vector<int>& P, const vector<int>& U, const vector<tuple<int, int, int>>& res) {
			vector<long long> bs(B.size());
			for (int i = 0; i < res.size(); i++) {
				long long total = get<0>(res[i]) + get<1>(res[i]) + get<2>(res[i]);
				Assert::AreEqual(total, (long long)P[i]);
				Assert::IsTrue(get<1>(res[i]) <= U[i]);
				Assert::IsTrue(get<0>(res[i]) >= 0);
				Assert::IsTrue(get<1>(res[i]) >= 0);
				Assert::IsTrue(get<2>(res[i]) >= 0);
				bs[i] += get<0>(res[i]);
				bs[i+1] += get<2>(res[i]);
				Assert::IsTrue(bs[i] <= B[i]);
			}
			Assert::IsTrue(bs.back()<= B.back());
		}
		int x;
		vector<int> B,P, U;
		TEST_METHOD(TestMethod11)
		{
			B = { 10,15,10 },P = { 20,20 },U = { 0,0 };
			long long llBuy=0;
			auto res = Solution().Do(llBuy,B,vector<int>(P),U);
			Assert::AreEqual(0LL, llBuy);
		}
		TEST_METHOD(TestMethod12)
		{
			long long llBuy=0;
			B = { 10,15,10 },P = { 20,20 },U = { 0,11 }				;
			auto res = Solution().Do(llBuy, B, vector<int>(P), U);
			Assert::AreEqual(5LL, llBuy);
			Check(B, P, U, res);
		}	
		TEST_METHOD(TestMethod13)
		{
			B = { 2,2,2,2 }, P = { 3,3,4 }, U = { 20,20,20 };
			long long llBuy = 0;
			auto res = Solution().Do(llBuy, B, vector<int>(P), U);
			Assert::AreEqual(2LL, llBuy);
			Check(B, P, U, 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++**实现。