526互联

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

发布时间 2023-08-01 16:27:23作者: 突破铁皮

题目大意为给定一个伤害k，n个怪物，hp为hp[i],每次都攻击hp最高的怪物，输出怪物的死亡顺序，如果攻击次数一样则按序号由小到大

解法：每次攻击都选最大的，假设hp=k*m+r,我们可以得到当进行m次攻击后，hp只有剩余数，再进行一次攻击怪物就会死亡，因此我们只需按余数由小到大排序即可，注意余0的话需要写成k为最大的

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N=3e5+10;
int t,n,k;
struct Monster{
	int h;
	int idx;
	bool operator<(const Monster& other) const{
		if(this->h%k!=other.h%k){
		int a=this->h%k==0? k:this->h%k;
		int b=other.h%k==0? k:other.h%k;
		return  a>b;
	}
		return this->idx<other.idx;	
	}
};
vector<Monster> mon;
void solve(){
	cin>>n>>k;
	mon.clear();
	for(int i=1;i<=n;i++){
		int h;
		cin>>h;
		mon.push_back({h,i});
	}
	sort(mon.begin(),mon.end());
	for(Monster i:mon){
		cout<<i.idx<<" ";
	}
	cout<<endl;
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
	solve();
}
}