B. Knights of a Polygonal Table
1.題意
給定n個(gè)騎士,每人都有自己的武力值和若干金幣,如果第一個(gè)騎士的武力值大于第二個(gè)騎士,那么第一個(gè)騎士就能獲取第二個(gè)騎士的所有金幣,每個(gè)騎士最多只能擊敗k個(gè)騎士。對(duì)于每個(gè)騎士,求出
決斗后他的金幣的最大值。
2.題解
結(jié)構(gòu)體存騎士的信息,顯然k最小,就以武力值排序,找到比他武力值小的所有騎士,然后用優(yōu)先隊(duì)列動(dòng)態(tài)維護(hù)這些騎士金錢前k大的即可。
3.代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int n, m, a[maxn];
ll ans[maxn];
struct knight {
int pow, coin, index;
knight() {
index = pow = coin = 0;
}
}k[maxn];
struct node {
priority_queue<int>q;
ll sum;
}ss;
bool cmp(knight a, knight b) {
return a.pow < b.pow;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &k[i].pow);
a[i] = k[i].pow;
}
for(int i = 1; i <= n; i++) {
scanf("%d", &k[i].coin);
k[i].index = i;
}
if(m == 0) {
for(int i = 1; i <= n; i++) {
printf("%d ", k[i].coin);
}
return 0;
}
if(n == 1) {
printf("%d ", k[1].coin);
return 0;
}
sort(k + 1, k + n + 1, cmp);
for(int i = 1; i <= m + 1; i++) {
for(int j = 1; j <= i; j++) {
ans[k[i].index] += (ll)k[j].coin;
}
}
for(int i = 1; i <= m; i++) {
ss.q.push(-k[i].coin);
ss.sum += k[i].coin;
}
if(k[m + 1].coin > -ss.q.top()) {
ss.sum -= -ss.q.top();
ss.q.pop();
ss.q.push(-k[m + 1].coin);
ss.sum += k[m + 1].coin;
}
for(int i = m + 2; i <= n; i++) {
ans[k[i].index] += k[i].coin;
ans[k[i].index] += ss.sum;
if(k[i].coin > -ss.q.top()) {
ss.sum -= -ss.q.top();
ss.q.pop();
ss.q.push(-k[i].coin);
ss.sum += k[i].coin;
}
}
for(int i = 1; i <= n ; i++) {
printf("%lld ", ans[i]);
}
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)