【Codeforces Round #488 by NEAR (Div. 2) B. Knights of a Polygonal Table】k最大是10， 按照power排序后 维护每个位置的前k大，注意k为0的情况
类似前缀和，每个位置的优先队列按照从小到大的顺序排列，同时保证队列的大小不超过k
#include
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, greater > > mp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k;
for (int i=0;
i>node[i].power;
node[i].id=i;
}for (int i=0;
i>node[i].money;
}sort(node, node+n);
for (int i=0;
i= 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 推荐阅读
- POJ 1027 The Same Game 模拟题
- CodeForces - 1102B（Array K-Coloring（给数字涂颜色））
- CodeForces1102B--Array K-Coloring--思维
- 模拟|【离散化扫描】 校门外的树{加强版}
- codeforce 469 B C -模拟 -构造
- Codeforces Round #531 (Div. 3) D Balanced Ternary String【模拟】
- zoj Capture the Flag 比较难的模拟题
- 模拟考试|济南刷题冲刺 Day2 下午
- bzoj1033: [ZJOI2008]杀蚂蚁antbuster