배틀로얄 19639

문제

접근 방법

가장 효율적으로 이득을 보려면 가능한 많은 데미지를 입고 죽기 직전에 치료하는 것이 좋을 것이다.

데미지를 가장 큰 값부터 사용해 준 뒤 체력이 남았다면 가장 낮은 값을 사용해 준다.
그렇게 되면 0에 가까운 양수가 될 것이고 그 상태에서 최대 체력을 넘지 않는 선에서 체력을 회복하면 될 것이다. 회복도 가장 큰 값부터 사용해 주고 최대 체력을 넘으려 하면 작은 값부터 사용하는 방식으로 생각했다.

이길 방법이 없는 경우는 체력 아이템을 다 사용했는데도 체력 아이템이 필요한 경우이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int X, Y, M, curHp, i = 1, j;
    vector<pii> damage, heal;
    vector<int> ret;
    cin >> X >> Y >> M;
    int startD = 0, endD = X - 1, startH = 0, endH = Y - 1;
    curHp = M;
    while (X--)
    {
        cin >> j;
        damage.push_back({j, i++});
    }
    sort(damage.begin(), damage.end());
    i = 1;
    while (Y--)
    {
        cin >> j;
        heal.push_back({j, i++});
    }
    sort(heal.begin(), heal.end());
    while (startD <= endD)
    {
        pii curNode = damage[endD];
        if (curNode.first < curHp)
        {
            ret.push_back(-curNode.second);
            curHp -= curNode.first;
            --endD;
            continue;
        }
        curNode = damage[startD];
        if (curNode.first < curHp)
        {
            ret.push_back(-curNode.second);
            curHp -= curNode.first;
            ++startD;
            continue;
        }
        if (startH > endH)
        {
            cout << 0;
            return 0;
        }
        curNode = heal[endH];
        if (curNode.first + curHp <= M)
        {
            ret.push_back(curNode.second);
            curHp += curNode.first;
            --endH;
            continue;
        }
        curNode = heal[startH];
        ret.push_back(curNode.second);
        curHp += curNode.first;
        ++startH;
    }
    for (int r : ret)
        cout << r << "\n";
    while (startH <= endH)
        cout << heal[startH++].second << "\n";
    return 0;
}

풀이

우선순위 큐든 뭐든 간에 잃은 체력과 회복 아이템의 가장 큰 값과 작은 값을 관리해 주면서 최대한의 이득을 보면 된다.
출력의 경우 방법이 없으면 0을 출력해야 하므로 바로바로 출력하지 않고 저장해 두었다가 출력해 준다.