B. Knights of a Polygonal Table

题目链接

Codeforces Round #488 by NEAR (Div. 2)--B. Knights of a Polygonal Table

题解

简单题。题意大概是有一组武士,每个可以杀掉k个比自己武力值低的其他武士,每个武士有一定金币,杀掉其他武士可以获得他的金币。求每个武士可能获得的最大金币。
将武力值排序后用优先队列维护金币数量即可,注意最终答案较大,应使用long long。

代码

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int n, k;
pair<int,int> a[100005];
priority_queue<int> que;
priority_queue<int> temp;
int mon[100005];
long long ans[100005];
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        a[i].second = i;
        cin >> a[i].first;
    }
    for (int i = 1; i <= n; i++) {
        cin >> mon[i];
        ans[i] = mon[i];
    }
    sort(a + 1, a + n + 1);
    que.push(mon[a[1].second]);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; (j <= k)&&que.size(); j++) {
            ans[a[i].second] += que.top();
            temp.push(que.top());
            que.pop();
        }
        for (; temp.size();) {
            que.push(temp.top());
            temp.pop();
        }
        que.push(mon[a[i].second]);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
}

标签: implementation, sortings, greedy

添加新评论