题解

一、题意

有 (n) 个怪物，第 (i) 个怪物血量为 (a_i)。每次操作：

1. 选出当前血量最高的怪物；若血量相同，选编号最小的；
2. 对其造成 k 点伤害；
3. 若血量小于等于0，怪物死亡，记录其编号。

重复直到所有怪物死亡，输出死亡顺序。

。

二、思路

这道题数据范围很小，n的总和不超过3000，而且k的范围是10000到100000，基本上砍怪1-2刀，怪就死了。 直接​每轮扫描找最大、减 k、死亡就记录，用严格大于 > 处理平局，即可 AC。 不需要排序、不需要堆、不需要任何高级数据结构。

平局怎么处理？

题目要求“血量相同选编号小的”。

扫描时让 i 从 (1) 到 (n)，只有满足 a[i] > mx 时才更新 mx：

• 遇到更大的血量，更新；
• 遇到相同血量，不更新（因为先遇到的是编号更小的，正好符合题意）。

三、参考代码（C++）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll t;
	cin>>t;
	while(t--){
		ll n,k;
		cin>>n>>k;
		ll a[n+1];
		
		vector<ll>r;
		
		for(ll i=1;i<=n;i++){
			cin>>a[i];		
		}
		ll cnt=0;
		while(cnt!=n){
			ll mx=0;
			ll index=0;
			for(ll i=1;i<=n;i++){
				if(a[i]>mx){
					mx=a[i];
					index=i;
				}
			}
			a[index]-=k;
			if(a[index]<=0){
				cnt++;
				r.push_back(index);
			}
			
		}
		for(ll i=0;i<n;i++){
			cout<<r[i]<<' ';
		}cout<<'\n';
		
	}
}