[补题记录] Codeforces Round 904 (Div. 2)（C）

本文主要是介绍[补题记录] Codeforces Round 904 (Div. 2)（C），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

URL：https://codeforces.com/contest/1884

目录

C

Problem/题意

Thought/思路

Code/代码

---

C

Problem/题意

有一个长度为 M 的序列，初始值都为 0。

现在给出 N 个区间 [l, r]，当选择某个区间时，可以让该区间内的数都 + 1。

对于每一种选择方案，其代价为：最大的数 - 最小的数。

问如何选择区间，使得代价最大。

Thought/思路

最核心的一点就是：不相交的两个区间，无法为答案带来任何贡献。

所以我们维护的方案，其内的区间，一定都是相交的：

• 那么对于最终答案而言，一定会选中 N 个区间中的某一个，所以只需要对每一个区间都判断当前有多少个区间与其相交即可，这样能求出最大值。
• 最小值的维护只需要通过判断相交的区间中，有多少个包含了 1 或者 m，取 1 或者 m 位置的最小值即可。

既然要求方案内区间是相交的，所以我们可以使用优先队列，队列大小就是最大值，出队入队过程中又可以维护 1 或者 m 的大小。

Code/代码

#include "bits/stdc++.h"#define int long long
#define pii std::pair<int, int>
#define x first
#define y secondint n, m;void solve() {std::cin >> n >> m;std::vector <pii> v(n + 1);for (int i = 1; i <= n; ++ i) {std::cin >> v[i].x >> v[i].y;}std::sort(v.begin() + 1, v.end(), std::less<pii>());std::priority_queue <pii, std::vector<pii>, std::greater<pii>> pq;int ans = 0, l = 0, r = 0;for (int i = 1; i <= n; ++ i) {while (!pq.empty()) {auto tmp = pq.top(); if (tmp.x < v[i].x) {pq.pop();if (v[tmp.y].x == 1) l --;if (v[tmp.y].y == m) r --;} else {break;}}pq.push({v[i].y, i});if (v[i].x == 1) l ++;if (v[i].y == m) r ++;ans = std::max(ans, pq.size() - std::min(l, r));}std::cout << ans << "\n";
}signed main() {int t; std::cin >> t;while (t --) {solve();}
}

这篇关于[补题记录] Codeforces Round 904 (Div. 2)（C）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---