読者です 読者をやめる 読者になる 読者になる

SRM 617 Div2 Medium SlimeXSlimonadeTycoon

問題

SRM 617 - TopCoder Wiki

i日目の朝にmorning[i]だけのSlimonadesを生産でき,customers[i]の顧客がSlimonadesを求めに来る. i日目の朝,i-stale_limit日前に生産されたSlimonadesは腐っていて廃棄しなくてはいけない. N日間に売ることの出来る最大のSlimonadesの数を答える問題.

解答

  • 腐らせることに対するペナルティがないので,毎朝,可能な数だけSlimonadesを生産するのが最適.
  • また,i-stale_limit日前に生産されたSlimonadesは腐るので,顧客には一番古いSlimonadesから渡していくのが最適.
  • 上記の戦略によってどれだけ売れるのかをシミュレーションして計算する.
class SlimeXSlimonadeTycoon
{
public:
  int sell(vector <int> morning, vector <int> customers, int stale_limit)
    {
      int n = morning.size();
      vector<int> prevs(stale_limit, 0);
      int cur = 0;
      int res = 0;
      for (int i = 0; i < n; i++){
        prevs[cur] = morning[i];
        for (int j = 0; j < stale_limit && customers[i] > 0; j++){
          int idx = (cur + j + 1)%stale_limit;
          if (customers[i] > prevs[idx]) {
            customers[i] -= prevs[idx];
            res += prevs[idx];
            prevs[idx] = 0;
          }else {
            prevs[idx] -= customers[i];
            res += customers[i];
            customers[i] = 0;
          }
        }
        cur = (cur + 1) % stale_limit;
      }
      return res;
    }
};