首页 > 代码库 > HDU 4546 比赛难度(优先队列)
HDU 4546 比赛难度(优先队列)
HDU 4546 比赛难度
题目链接
思路:由于m不是很大,如果用一个优先队列维护,如果每次能保证加入的值是最小的,那么只需要加入m次就能完成了,时间复杂度足够,那么如何保证呢,就把数列排序,维护优先队列为当前和加下一个位置和的最小值,每次一个出队,把下一个位置取于不取在入队,最后求出答案即可
代码:
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int N = 10005; int t, n, m, a[N]; struct Node { int sum, nextsum, nextid; Node() {} Node(int sum, int nextsum, int nextid) { this->sum = sum; this->nextsum = nextsum; this->nextid = nextid; } bool operator < (const Node &c) const { return nextsum > c.nextsum; } }; const int INF = 0x3f3f3f3f; int main() { int cas = 0; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); priority_queue<Node> Q; Q.push(Node(0, a[0], 0)); int cnt = 0; while (!Q.empty()) { Node u = Q.top(); Q.pop(); if (u.nextid >= n) continue; Q.push(Node(u.sum, u.sum + a[u.nextid + 1], u.nextid + 1)); Q.push(Node(u.nextsum, u.nextsum + a[u.nextid + 1], u.nextid + 1)); cnt++; if (cnt == m) { printf("Case #%d: %d\n", ++cas, u.nextsum); break; } } } return 0; }
HDU 4546 比赛难度(优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。