陈仓区人民政府,重生纨绔子,平顶山新闻网
p3028 [usaco10oct]汽水机soda machine
差分,看到\(a[i]\leq 1e9\),离散化一下,在\(l\)处\(+1\),\(r+1\)处\(-1\),这样就只有\(2n\)个点了,再按位置排一下序,扫一遍记录答案就可以了。
需要注意的是,如果在某个位置既有\(+1\)操作又有\(-1\)操作,要先\(-1\)再\(+1\),否则在统计答案的时候会多算
#include <bits/stdc++.h> using namespace std; const int n = 1e6 + 10; int sum, ans, n; struct node { int pos, val; bool operator<(const node & oth) const { return pos == oth.pos ? val < oth.val : pos < oth.pos; } } e[n]; int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1, x, y; i <= n; ++i) { cin >> x >> y; e[i] = (node) {x, 1}, e[i + n] = (node) {y + 1, -1}; } sort(e + 1, e + 1 + n + n); for (int i = 1; i <= n + n; ++i) { sum += e[i].val; ans = max(ans, sum); } cout << ans; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论