蓝桥杯2022年第十三届决赛真题-打折（C/C++/Java组）

解题思路:
记录所有物品在哪一天开始打折，在哪一天结束打折

离散化所有时间，先暴力所有物品未打折的最小值(使用multiset快速找出)，再枚举每一天，计算贡献，快速得出当天花费的最小值，最终即可得出答案

代码有注释
注意事项:
打折时间为[s, t]，意味着第t+1天才结束打折
参考代码:

#include <bits/stdc++.h>
using namespace std;

// 2023 OneWan

const int MAXM = 100000 + 5;
int s[MAXM], t[MAXM], p[MAXM], c[MAXM]; // 对应题目输入的各数组
multiset<long long> st[MAXM]; // st[i] 为 物品 i 在所有商店的价格
vector<vector<pair<int, int>>> v(MAXM); // v[i][j] 为 商店 i 出售的 第 j 个物品

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> time; // 用于离散化 时间
	for (int i = 0 ; i < m ; i++) {
		cin >> s[i] >> t[i] >> p[i] >> c[i];
		time.emplace_back(s[i]);
		time.emplace_back(t[i] + 1); // 打折是闭区间 所以需要+1才是没有打折截止
		for (int j = 0 ; j < c[i] ; j++) {
			int a, b; // 物品编号及原价
			cin >> a >> b;
			v[i].emplace_back(a, b);
		}
	}
	sort(time.begin(), time.end()); // 排序时间
	time.resize(unique(time.begin(), time.end()) - time.begin()); // 离散化时间
	auto get = [&](int t) {
		return lower_bound(time.begin(), time.end(), t) - time.begin();
	}; // 获取离散化后的下标
	int len = time.size();
	vector<vector<pair<int, int>>> startD(len), endD(len);
	// startD[i] 为 第 i 天 开始打折的物品编号 和 打折后的价格
	// endD[i] 为 第 i 天 结束打折的物品编号 和 打折后的价格
	for (int i = 0 ; i < m ; i++) {
		int starts = get(s[i]), ends = get(t[i] + 1); // 获取打折开始与结束时间离散化后的下标
		for (auto& [x, y] : v[i]) {
			int t = 1LL * y * p[i] / 100; // 打折后的价格
			st[x].insert(y); // 把物品原价放入
			startD[starts].emplace_back(x, t);
			endD[ends].emplace_back(x, t);
		}
	}
	long long temp = 0; // 用于存每天购买所有物品所用的价格
	for (int i = 1 ; i <= n ; i++) temp += *st[i].begin(); // 计算不进行打折时购买所有物品所用的价格
	long long ans = temp;
	for (int i = 0 ; i < len ; i++) {
		long long k = 0; // 打折与不打折对价格的贡献
		for (auto& [x, y] : startD[i]) { // 遍历当天所有开始打折的物品 打折前价格最小值为a, 打折后价格最小值为b, 贡献为b - a
			k -= *st[x].begin();
			st[x].insert(y);
			k += *st[x].begin();
		}
		for (auto& [x, y] : endD[i]) { // 遍历当天所有结束打折的物品 打折前价格最小值为a, 打折后价格最小值为b, 贡献为b - a
			k -= *st[x].begin();
			int t = st[x].count(y);
			st[x].erase(y);
			for (int j = 1 ; j < t ; j++) st[x].insert(y);
			k += *st[x].begin();
		}
		temp += k; // 加上贡献, 由前一段转移到后一段
		ans = min(ans, temp); // 找花费最小
	}
	cout << ans;
	return 0;
}