+ 问题描述
+ Link: https://codeforces.com/contest/994/problem/B
+ 描述
Unlike Knights of a Round Table, Knights of a Polygonal Table deprived of nobility and happy to kill each other. But each knight has some power and a knight can kill another knight if and only if his power is greater than the power of victim. However, even such a knight will torment his conscience, so he can kill no more than kk other knights. Also, each knight has some number of coins. After a kill, a knight can pick up all victim's coins.
Now each knight ponders: how many coins he can have if only he kills other knights?
You should answer this question for each knight.
+ 大意
n个骑士, 每个骑士有战力p, 钱c, 每个骑士可以抢战力比他低的钱, 每个骑士最多抢k次, 对每个骑士求出最大钱数。
+ 输入
The first line contains two integers nn and kk (1≤n≤10^5,0≤k≤min(n−1,10))(1≤n≤10^5,0≤k≤min(n−1,10)) — the number of knights and the number kk from the statement.
The second line contains nn integers p1,p2,…,pn (1≤pi≤10^9)(1≤pi≤10^9) — powers of the knights. All pipi are distinct.
The third line contains nn integers c1,c2,…,cn (0≤ci≤10^9)(0≤ci≤10^9) — the number of coins each knight has.
+ 输出
Print nn integers — the maximum number of coins each knight can have it only he kills other knights.
+ 样例
+ 网友思路
1 贪心 +(优先队列)
2 线段树
n ...
+ 代码
【程序结果：用例未完全通过，本博文仅为暂存代码之目的】
/*
B. Knights of a Polygonal Table
url:http://codeforces.com/problemset/problem/994/B
思路：
step0.对骑士进行编号
step1.按照权力值进行顺序排序
step2.分别计算骑士所能杀死的其他骑士及其对应的金币值
step3.按照编号重新恢复原始排序.
*/
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std; typedef struct Knight{
int id;
int power;
int coins;
int expected_coins;
}Knight; bool compare_id(Knight a, Knight b){
if(a.id>b.id)
return false;
else return true;
} bool compare_power(Knight a, Knight b){
if(a.power>b.power)
return false;
else return true;
} int main(){
int n,k,id = 0;
Knight *persons;
scanf("%d %d", &n, &k);
persons = (Knight*)malloc(n*sizeof(Knight));
//printf("\n%d %d", k, n);
for(int i=0;i<n;i++){
persons[i].id = ++id;
scanf("%d", &(persons[i].power));
}
for(int i=0;i<n;i++){
scanf("%d", &(persons[i].coins));
} sort(persons, persons+n, compare_power);//顺序排序：<algorithm> for(int i=0;i<n;i++){//分别计算各骑士能够杀死的人和可以获得的金币最大值
persons[i].expected_coins = persons[i].coins;
for(int j=1;j<=k;j++){
if(i - j >= 0){
persons[i].expected_coins += persons[i - j].coins;
}
}
} sort(persons, persons+n, compare_id);//依照id恢复原始排序 for(int i=0;i<n;i++){
printf("%d%s", persons[i].expected_coins, ((i + 1) != n ?" ":"\n"));//test
//printf("%d %d %d\n", persons[i].power, persons[i].coins, persons[i].expected_coins);//test
} return 0;
}