Algoogle

Algorithm for Programming Contest

AOJ 2236 Rabbit Plays Games!

Category: AOJ Tag: greedy

Rabbit Plays Games!

問題概要


自分とn体の敵がいる.
それぞれHP,攻撃力,防御力,素早さのステータスをもつ.
それぞれ素早さが高い順に攻撃できる.
攻撃力がaのキャラが防御力dのキャラに攻撃して与えるダメージはmax(0,a-d)である.
自分が受けるダメージの最小を答えよ.
ただしそれが自分のHPより大きい場合は-1を出力せよ.

解法


倒していく順番を考える.
敵iを倒すのにかかるターン数をAi, 1回あたり食らうダメージをBiとする.
敵iを倒して,敵jを残す時,敵jから食らうダメージがAi*Bjだけ増える.
逆の順ならAj*Biだけ増える.
この増加量の大小関係は推移する.
これは各値は正とすれば
Ai*Bj < Aj*Bi
なら両辺をBi,Bjで割れば
Ai/Bi < Aj/Bj
となり明らか.
これが小さくなる順に倒せば良い.

ただし,自分が相手にダメージを与えられない場合と,相手が自分にダメージを与えられない場合に留意すること.

コード


(2236.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 40010;

int n, h[N], a[N], d[N], s[N], id[N];

inline i64 attack(int i) { return (h[i]+a[0]-d[i]-1)/(a[0]-d[i]);}
inline i64 damage(int i) { return max(0, a[i]-d[0]);}

bool cmp(int i, int j)
{
        const i64 Ai = attack(i), Aj = attack(j);
        const i64 Di = Ai*damage(j), Dj = Aj*damage(i);
        return Di < Dj;
}

int solve()
{
        int m = 0;
        for (int i = 1; i <= n; i++) {
                if(a[0] <= d[i] and a[i] > d[0]) return -1;
                if(a[0] > d[i]) id[m++] = i;
        }
        sort(id,id+m,cmp);
        i64 turn = 0, sum = 0;
        for (int i = 0; i < m; i++) {
                i64 atk = attack(id[i]), dmg = damage(id[i]);
                sum += (turn+atk)*dmg;
                if(s[id[i]] < s[0]) sum -= dmg;
                if(h[0] <= sum) return -1;
                turn += atk;
        }
        return sum;
}

void input()
{
        scanf("%d", &n);
        for (int i = 0; i <= n; i++) scanf("%d%d%d%d", h+i, a+i, d+i, s+i);
}

int main()
{
        input();
        printf("%d\n", solve());
        return 0;
}

Comments