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

本文主要是介绍Codeforces Round #488 by NEAR (Div. 2) B. Knights of a Polygonal Table，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

k最大是10， 按照power排序后 维护每个位置的前k大，注意k为0的情况
类似前缀和，每个位置的优先队列按照从小到大的顺序排列，同时保证队列的大小不超过k

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e6 + 10;
const int N = maxn;
typedef long long ll;
#define gcd __gcdstruct Node
{int power;int id;int money;bool operator<(const Node& rhs){return power < rhs.power;}
} node[N];ll index[N];map<int, priority_queue<int, vector<int>, greater<int> > > mp;int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,k;cin>>n>>k;for (int i=0; i<n; i++){cin>>node[i].power;node[i].id=i;}for (int i=0; i<n; i++){cin>>node[i].money;}sort(node, node+n);for (int i=0; i<n; i++){if (i==0);else{mp[i] = mp[i-1];if (mp[i].size() >= k){if (k){int tmp = mp[i].top();if (tmp < node[i-1].money){mp[i].pop();mp[i].push(node[i-1].money);}}}else{mp[i].push(node[i-1].money);}}}for (int i=0; i<n; i++){ll t = node[i].money;while (!mp[i].empty()){t+=mp[i].top();mp[i].pop();}index[node[i].id] = t;}for (int i=0; i<n; i++){printf("%lld ", index[i]);}return 0;
}

这篇关于Codeforces Round #488 by NEAR (Div. 2) B. Knights of a Polygonal Table的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---