题目
p2352 队爷的新书
解析
题目意思是
给你n个区间,选择一个数x,使\(x\times覆盖x的区间的个数\)最大
和差不多
差分,离散化一下,在区间的\(l\)处\(+1\),\(r+1\)处\(−1\),不同的是,我们要求的是最大乘积,显然相同的覆盖数下,\(i\)越大,答案就越大,所以我们在\(r\)处\(+0\),表示这个位置不参与操作,只是用来贡献答案,然后排序扫一遍就可以了
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int n = 1e6 + 10; int n, ans, mx, sum; struct node { int a, b; bool operator <(const node &oth) const { return a < oth.a; } } e[n]; signed main() { cin >> n; for (int i = 1, x, y; i <= n; ++i) { cin >> x >> y; e[++mx] = (node) {x, 1}; e[++mx] = (node) {y, 0}; e[++mx] = (node) {y + 1, -1}; } sort(e + 1, e + 1 + mx); for (int i = 1; i <= mx; ++i) { sum += e[i].b; ans = max(ans, sum * e[i].a); } cout << ans; }