wordpress多人聊天室,站长网seo综合查询工具,2023前端开发的就业现状,珠海免费建站目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解 一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
1884C - Medium Design 二、解题报告
1、思路分析
考虑 最大值 和 最小值…目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解 一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
1884C - Medium Design 二、解题报告
1、思路分析
考虑 最大值 和 最小值的位置 mai, mii
对于 一个 包含 mai 的线段我们选择
如果 该线段包含 mii答案不会变大
如果 该线段不包含 mii答案会 1
也就是说对于所有的包含 mai 的线段我们拿进来不会使得答案变差
同时包含 maimii 的线段我们可以不拿
那么我们说明 最优解 的 mii 一定在 两端
我们按照 mii 在左端 和 右端 的情况分别计算求最值即可
以mii 0为例我们对于所有左端点不为0的线段按左右端点双关键字排序跑差分
维护被覆盖次数最多的点的次数维护最值即可
2、复杂度 时间复杂度 O(nlogn)空间复杂度O(n) 3、代码详解
#include bits/stdc.h// #define DEBUGusing u32 unsigned;
using i64 long long;
using u64 unsigned long long;constexpr int inf32 1E9 7;
constexpr i64 inf64 1E18 7;void solve() {int n, m;std::cin n m;std::vectorint l(n), r(n);for (int i 0; i n; i) {std::cin l[i] r[i];-- l[i];}std::vectorstd::pairint, int segs;for (int i 0; i n; i) {if (l[i] 0) {segs.emplace_back(l[i], 1);segs.emplace_back(r[i], -1);}}int ans 0;int cur 0, lst 0;std::ranges::sort(segs);for (auto [x, y] : segs) {if (x lst) {ans std::max(ans, cur);}lst x; cur y;}if (m lst) {ans std::max(ans, cur);}segs.clear();for (int i 0; i n; i) {if (r[i] m) {segs.emplace_back(l[i], 1);segs.emplace_back(r[i], -1);}}std::ranges::sort(segs);cur 0, lst 0;for (auto [x, y] : segs) {if (x lst) {ans std::max(ans, cur);}lst x;cur y;}if (m lst) {ans std::max(ans, cur);}std::cout ans \n;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint add clock();freopen(in.txt, r, stdin);freopen(out.txt, w, stdout);
#endifint t 1;std::cin t;while (t--) {solve();}
#ifdef DEBUGstd::cerr run-time: clock() - add \n;
#endifreturn 0;
}
