首页 > 代码库 > HDU 5700 优先队列(或者multiset) 或 线段树
HDU 5700 优先队列(或者multiset) 或 线段树
题目大意:有n个区间,求k个区间,使得这k个区间相交的区间内数字之和最大。数列的数字均>=0
优先队列思路:
按照左端点sort,然后枚举左端点,假设他被覆盖过k次,然后用优先队列来维护最右端即可。
//看看会不会爆int!数组会不会少了一维! //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha\n") const int maxn = 100000 + 5; int n, k, m; LL a[maxn], sum[maxn]; vector<int> ve[maxn]; struct Point{ int rb; bool operator < (const Point& a) const{ return a.rb < rb; } Point(int x = 0): rb(x){}; }; int main(){ while (scanf("%d%d%d", &n, &k, &m) == 3){ memset(sum, 0, sizeof(sum)); for (int i = 1; i <= n; i++){ scanf("%lld", a + i); sum[i] = sum[i - 1] + a[i]; ve[i].clear(); } for (int i = 1; i <= m; i++){ int u, v; scanf("%d%d", &u, &v); ve[u].push_back(v); } LL ans = 0; priority_queue<Point> que; for (int i = 1; i <= n; i++){ for (int j = 0; j < ve[i].size(); j++){ que.push(Point(ve[i][j])); } while (que.size() > k) que.pop(); if (que.size() == k) ans = max(ans, sum[que.top().rb] - sum[i - 1]); } printf("%lld\n", ans); } return 0; }
线段树思路:(明天早上增加)
HDU 5700 优先队列(或者multiset) 或 线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。