TCO11 Qual3 Medium(500) CoinMachinesGame

CoinMachinesGame

need[i]-give[i]が小さいマシンから順に使っていけば良い。

#include <vector>
using namespace std;

class CoinMachinesGame{public:
int maxGames( int coins, vector <int> need, vector <int> give )
{
    int n = (int)need.size();

    int ans = 0;

    while ( true )
    {
        int m = -1;
        for ( int i=0; i<n; i++ )
            if ( need[i]<=coins  &&
                 ( m==-1 || need[i]-give[i]<need[m]-give[m] ) )
                m = i;
        if ( m==-1 )
            break;

        int t = (coins-need[m])/(need[m]-give[m])+1;
        ans += t;
        coins -= (need[m]-give[m])*t;
    }

    return ans;
}};