SRM479 Div1 Easy(250) TheCoffeeTimeDivOne
茶とコーヒーを同時にフラスコに入れることはできない。それぞれ遠い方から順に7人ずつ配っていけば良い。コーヒーは、まず茶の乗客を除いて考え、茶の乗客を間に入れることで移動距離が増える乗客の数を足していく。
国際線でコーヒーを頼むと、コーヒーの発音がcoffeeよりcokeに近いので、コーラが出てくるらしい。
#include <vector> #include <algorithm> using namespace std; class TheCoffeeTimeDivOne { public: long long find( int n, vector <int> tea ); }; long long TheCoffeeTimeDivOne::find( int n, vector <int> tea ) { int m = (int)tea.size(); long long s = 0; // 移動時間(茶) sort( tea.begin(), tea.end() ); for ( int i=m-1; i>=0; i-=7 ) s += tea[i] * 2; // 移動時間(コーヒー) s += (long long)( n-m + (n-m-1)%7+1 ) * ( (n-m+6)/7 ) / 2 * 2; for ( int i=0; i<m; i++ ) s += (n-m+i-tea[i]+1+6)/7 * 2; // 客に飲み物を渡す時間 s += 4 * n; // フラスコに飲み物を入れる時間 s += ( (m+6)/7 + (n-m+6)/7 ) * 47; return s; }