這是 CF #552 輪 C 題,人生第一場 CF 比賽,就卡在這題上了,紀念一下吧。題目標簽是 數學 和 模擬,屬於 1400 等級的題。雖然看到題目有點想法,想用指針追蹤數組,但是在打比賽的時候,實現起來感覺還是好複雜,刷題太少吧,看完題解才明白原來可以這麽做。Gourmet Cat 可以翻譯爲 美食家貓貓/

題目概述

一隻美食家貓貓吃特定食物基於特定日期:

  • 周一,周四,周日,吃魚肉
  • 周二,周六,吃兔肉
  • 一周裏的其他日子吃鷄肉

然後,他主人準備帶他一起去一趟旅行,背包裏有

  • a 日量的魚肉
  • b 日量的兔肉
  • c 日量的雞肉

主人會選擇一周中的一天出發,然後那一天必須滿足讓貓貓持續最長天數的進食,直到背包中沒有某樣食物。問貓貓在旅行中最長可以進食多少天?

輸入輸出

輸入 正整數 a,b,和 c 對應 魚肉,兔肉,和 鷄肉 的數量

輸出 貓貓能進食的最長天數

input 2 1 1
output 4

input 3 2 2
output 7

input 1 100 1
output 3

input 30 20 10
output 39

解題思路

這道題 數學 部分并不是很難,比較繞的部分在 模擬 實現上。思路上還是很簡單的,先去計算食物可堅持的最少周數,對比 a/3,b/2,和 c/2,用周數 weeks 來記錄,那麽剩餘量就是 a 中減去 3 * weeks,b 中減去 2 * weeks,c 中減去 2 * weeks。然後進行一周的模擬,從周一開始,一直到周日,用一個數組 idx 來表示每天的食物 idx = {1,2,3,1,3,2,1} (1 對應 魚肉,2 對應 兔肉,3 對應 鷄肉),這樣當指針 day 指到某一天的時候,day = day % 7 + 1,只需要從對應的 a,b,和 c 中減 1 即可,循環結束于要進食的食物等於 0。在這個過程中需要一個計數變量 count,去記錄最長天數。最後,答案的最長天數就是 7 * weeks + count。

小技巧:a,b,和 c 可以變爲一個數組 a[1],a[2],和 a[3],這樣并不影響最後的計算結果,只是更爲方便。

代碼實現

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
#ifdef _DEBUG
  freopen("in", "r", stdin);
//  freopen("out", "w", stdout);
#endif

  ios::sync_with_stdio(0);
  cin.tie(0);

  vi a(3);
  cin >> a[0] >> a[1] >> a[2];

  int weeks = min({a[0]/3, a[1]/2, a[2]/2});

  a[0] -= 3 * weeks;
  a[1] -= 2 * weeks;
  a[2] -= 2 * weeks;

  vi idx({0, 1, 2, 0, 2, 1, 0});

  int ans = 0;
  for (int i = 0; i < idx.size(); i++) {
    int day = i;
    vi b = a;

    int count = 0;
    while (b[idx[day]] != 0) {
      b[idx[day]] -= 1;
      count += 1;
      day = (day + 1) % 7;
    }

    ans = max(ans, 7 * weeks + count);
  }
  
  cout << ans << endl;
  return 0;
}