神秘餐馆题解(c++实现)

知识点:

1.贪心算法
2.前缀和

问题:

求连续去餐厅最多可以去几天,且第i%7天与i天选在菜得是一样的
(一开始我也没有想到是连续的,还想暴力枚举但是发现复杂度很高,也不好枚举)

算法基本思想:

我们只要关心最新的一天能吃到且价格最低就行
一.第i天去餐厅,
	1.如果i<=7,选最价格最低的菜
	2.不然,需要去看当前菜(i%7)--(i-7*k)--(i-7)的总价最小,简单的说就是选这个菜，还要考虑以前和现在选的总价(价格之和最低)

二.选完后可以用我们的钱减去新的花费
	如果减完后小于0说明这一天不能吃了
	大于等于0,说明还可以明天可能还可以吃(如果明天免费0还是可以吃的)

代码实现:

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cfloat>
#include<set>
#include<unordered_map>
using namespace std;


void solve() {
    int n, m, budget;
    cin >> n >> m >> budget;
    vector<vector<int>> price(n,vector<int>(m,0));
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            price[i][j] = s[j];
            if (s[j] >= '0' && s[j] <= '9')     price[i][j] = s[j] - '0';
            else if (s[j] >= 'A' && s[j] <= 'Z')   price[i][j] = s[j] - 'A'+10;
            else  price[i][j] = s[j] - 'a'+36;
        }
    }
    
    vector<int> recoed(7,0);
    for (int i = 0; i < n; i++)
    {
        int spend = 0;
        //小于7天直接选最小
        if (i < 7) {
            for (int j = 0; j < m; j++)
                if (price[i][j] < price[i][recoed[i]]) recoed[i] = j;
            spend = price[i][recoed[i]];
        }
        else {
            //求前缀和
            for (int j = 0; j < m; j++)
                price[i][j]+=price[i-7][j];
            // 选出最小花费的一道菜
            int old = recoed[i % 7];
            for (int j = 0; j < m; j++) {
                if (price[i][j] < price[i][recoed[i % 7]] ) recoed[i % 7] = j;
            }
            spend = price[i][recoed[i % 7]] - price[i-7][old];
        }

        budget -= spend;
        if (budget < 0) {
            cout << i;
            return;
        }

    }

    cout << n;
}


int main() {
    std::ios::sync_with_stdio(false); std::cin.tie(0);
    solve();
    return 0;
}

看完可以点赞一下，相互帮助提升算法能力