CF994B Knights of a Polygonal Table
题目描述
有 nnn 个骑士想决战。每个骑士都有能力值，且身上带有一些金币。如果骑士 AAA 的能力值大于骑士 BBB ，那么骑士 AAA 就可以杀死骑士 BBB ，并获得骑士 BBB 身上的所有金币。但就算是骑士也不会残忍过度，他们最多只会杀死 kkk 个骑士。对于每一位骑士，请你求出在决战后他身上金币的最大值。
输入格式
第 111 行，有 222 个整数，分别为骑士人数 nnn 和杀人数上限 kkk 。
（数据范围： 1⩽n⩽1051 leqslant n leqslant 10^{5}1⩽n⩽105 , 0⩽k⩽min(n−1, 10)0 leqslant k leqslant min(n - 1, 10)0⩽k⩽min(n−1, 10) ）
第 222 行，有 nnn 个整数，表示每个骑士的能力值 pip_ipi 。
第 333 行，有 nnn 个整数，表示每个骑士原有的金币 cic_ici 。
（数据范围： 1⩽pi⩽1091 leqslant p_i leqslant 10^{9}1⩽pi⩽109 , 0⩽ci⩽1090 leqslant c_i leqslant 10^{9}0⩽ci⩽109 ）
##输出格式
111 行内输出 nnn 个整数，决战后每个骑士身上金币的最大值，每两个数间以单个空格隔开。
##提示与说明
- 第 111 组样例的解释：
第 111 个骑士是最蒻的，因此他谁也不能杀，只能保留自己原有的金币。
第 222 个骑士只能杀死第 111 个骑士，因此他最多拥有 2+1=32 + 1 = 32+1=3 个金币。
第 333 个骑士是最蔃的，但他只能选择杀 k=2k = 2k=2 个骑士。显然他会杀死第 222 个骑士和 第 444 个骑士，因为他们身上的金币更多。因此他最多拥有 11+2+33=4611 + 2 + 33 = 4611+2+33=46 个金币。
第 444 个骑士应该杀死第 111 个和第 222 个骑士，因此他最多拥有 33+1+2=3633 + 1 + 2 = 3633+1+2=36 个金币。
- 第 222 组样例的解释：
除了最蒻的第 111 个骑士谁也不能杀，其他骑士都能杀死前一个骑士并获得他的金币。
- 第 333 组样例的解释：
由于只有一个骑士在决战中，他无法杀死任何人。
感谢@Sooke 提供翻译
题解：
感觉这些绿题都比上面的黄题简单呢...
很容易想的贪心策略：在所有自己能吃的骑士里，尽可能吃金币多的。（采用了CSP2020贪吃蛇的说法（滑稽））
贪心策略这么好想，我觉得应该是卡时间的，也就是卡依题意模拟。
后来发现根本不卡直接模拟的做法。不需要套什么平衡树，有病么？
直接按武力值大小排序，然后从头到尾维护一个大根堆来维护金币数量，再加一个编号的映射，就OK了啊。
时间复杂度级别在(O(nlog n))。完全可以通过本题。
于是开始思考有没有(O(n))做法，但是没想出来...（太菜了）
如果各路大神能想到这道题的数据加强版，请一定要联系我哦！我们交流一下思路。
代码：
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,k;
struct node
{
int p,c,ans,id;
}a[maxn];
priority_queue<int> q;
vector<int> v;
bool cmp(node a,node b)
{
return a.p<b.p;
}
bool cmp1(node a,node b)
{
return a.id<b.id;
}
signed main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i].p);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].c);
a[i].ans=a[i].c;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
q.push(a[1].c);
for(int i=2;i<=n;i++)
{
int s=q.size();
int t=min(k,s);
for(int j=1;j<=t;j++)
{
int x=q.top();
q.pop();
v.push_back(x);
}
for(int j=0;j<v.size();j++)
{
a[i].ans+=v[j];
q.push(v[j]);
}
v.clear();
q.push(a[i].c);
}
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)
printf("%lld ",a[i].ans);
return 0;
}