Codeforces #1480B The Great Hero

문제

https://codeforces.com/problemset/problem/1480/B

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

struct ability{
    int a;
    int b;
};

bool compare(ability a, ability b){
    return a.a < b.a;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        ll A, B;
        cin >> A >> B >> n;
        vector<ability> m(n);
        for(int i = 0; i < n; i++)
            cin >> m[i].a;
        for(int i = 0; i < n; i++)
            cin >> m[i].b;
        sort(all(m), compare);
        for(int i = 0; i < n; i++){
            float x = B;
            float y = m[i].b;
            ll hero = ceil(x/m[i].a);
            ll monster = ceil(y/A);
            if(hero >= monster){
                B -= m[i].a*monster;
                m[i].b -= A*monster;
            }
            else{
                break;
            }
        }
        int ma = -INF;
        for(int i = 0; i < n; i++){
            ma = max(ma, m[i].b);
        }
        if(ma <= 0) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

어차피 모든 몬스터들을 상대해야 하기 때문에 순서에 상관없이 싸움을 해도 최적해 일 것이라 잘못 생각했다.

-> 몬스터의 공격력이 약한 순서대로 싸워야 한다.

몬스터와 전투 상황에서 생길 수 있는 3가지 경우를 모두 찾았지만, 구현을 위한 설계 시간이 너무 오래 걸렸다.