2236-Rabbit Plays Games!

問題文

Rabbit Plays Games! | Aizu Online Judge

解法

二人の場合を考える
さらに自分はかならず先制攻撃と見なす．

1:倒すまでの時間t1 受けるダメージ a1
2:倒すまでの時間t2 受けるダメージ a2

1→2の順で倒す場合
(t1-1)a1+(t1+t2-1)a2

2→1の順で倒す場合
(t2-1)a2+(t1+t2-1)a1

1→2が2→1よりも良くなる条件を調べる
(t1-1)a1+(t1+t2-1)a2 >= (t2-1)a2+(t1+t2-1)a1
t1*a1-a1-a2+a2*t1+a2*t2 >= t2*a2-a2-a1+a1*t1+a1*t2
a2*t1 >= a1*t2
t1/a1 >= t2/a2
a1/t1<=a2/t2
a1*t2<=a2*t1

この順番に貪欲に倒していく

実装(C++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long lli;
struct Enemy{
	lli time,attack;
};
bool operator<(const Enemy &a,const Enemy &b){
	return b.attack*a.time<b.time*a.attack;
}
lli n;
lli h,a,d,s;
lli mh,ma,md,ms;
vector<Enemy> e;
lli calc(lli a,lli d){
	return max<lli>(a-d,0);
}
lli init;
int main() {
	cin>>n;
	cin>>mh>>ma>>md>>ms;
	init=mh;
	for(lli i=0;i<n;i++){
		cin>>h>>a>>d>>s;
		if(calc(ma,d)==0){//相手を倒せない
			if(calc(a,md)==0){
				continue;//こいつは無害
			}else{
				cout<<-1<<endl;
				return 0;
			}
		}
		e.push_back((Enemy){(h+calc(ma,d)-1)/calc(ma,d),calc(a,md)});
		if(s>ms){
			mh-=calc(a,md);
		}
	}
	stable_sort(e.begin(),e.end());
	lli now=0;
	for(lli i=0;i<(lli)e.size();i++){
		mh-=e[i].attack*(e[i].time-1+now);
		if(mh<0)break;
		now+=e[i].time;
	}
	if(mh<=0)mh=-1;else mh=init-mh;
	cout<<mh<<endl;
	return 0;
}