526互联

Educational Codeforces Round 152 (Rated for Div. 2) B. Monsters

发布时间 2023-10-18 04:12:47作者: zsxuan

有 \(n\) 个怪物，第 \(i\) 个怪物的血量为 \(a_i\) 。英雄一次攻击可以造成 \(k\) 点伤害，但只会攻击当前生命值最高的怪物。若有多个最高血量的怪物，则选择编号最小的怪物攻击。当怪物的血量 \(\leq 0\) 时则被消灭。

输出一个排列，表示怪物被消灭的编号顺序。

容易想到，当 \(\exists a_i > k\) ，不会有任何一只怪物死亡。于是第一个怪物死亡之前，\(n\) 个怪物的血量 \(\in [1, k]\) 。显然此时血量更高的怪物会被先消灭。

于是执行以下算法 \(\forall i, a_i \% = k, if\ a_i=0,\ a_i = k\) 。然后按大到小排序，并输出他们编号。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n, k; std::cin >> n >> k;
	std::vector<std::pair<int,int> > a(n);
	for (int i = 0; i < n; i++) {
		int x; std::cin >> x;
		x %= k;
		if (x == 0) x = k;
		a[i] = {x, i + 1};
	}
	std::sort(a.begin(), a.end(), [&](std::pair<int,int> X, std::pair<int,int> Y){
		if (X.first != Y.first) return X.first > Y.first;
		else return X.second < Y.second;
	});
	for (int i = 0; i < n; i++) std::cout << a[i].second << " \n"[i == n - 1];
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}