TCO11 Qual3 Medium(500) 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; }};