云短信平台优惠活动【华为OD机试 2023 Q1考试题 A卷】

题目描述：
   某云短信运营商，为庆祝国庆，推出充值优惠活动。现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
输入描述：第一行客户预算M，其中0 <= M <= 10^6
         第二行给出售价表，P1,P2,...Pn，其中 1 <= n <= 100，
         Pi为充值i元获得的短信条数。1 <= Pi <= 1000，1 <= n <= 100
输出描述：
最多获得的短信条数。

示例

示例1
输入输出示例仅供调试，后台判题数据一般不包含示例
输入：
6
10 20 30 40 60
输出：
70
说明：分两次充值最优，1元、5元各一次。总条数 10 + 60 = 70

示例2
输入：
15
10 20 30 40 60 60 70 80 90 150
输出：
210
说明：分两次充值最优，10元、5元各充一次。总条数 150 + 60 = 210

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> split_str(string params_str, string op = " ") {
    vector<int> res;
    while (params_str.find(op) != string::npos) {
        int found = params_str.find(op);
        res.push_back(stoi(params_str.substr(0, found)));
        params_str = params_str.substr(found + 1);
    }
    res.push_back(stoi(params_str));
    return res;
}

int main()
{
    // 客户预算 customer budget
    string mStr;
    getline(cin, mStr);
    int M = stoi(mStr);

    string priceStr;
    getline(cin, priceStr);
    // 售价表 price list
    vector<int> prices = split_str(priceStr);

    // 剩余的预算
    int rest = M;
    // 云短信总条数
    int smsNum = 0;
    // 贪心算法 从到大小遍历售价表，优先选择售价高的（售价高的短信条数也越多）
    for (int i = prices.size() - 1; i >= 0; i--) {
        if (rest <= 0) {
            break;
        }
        if (rest >= i + 1) {
            smsNum += prices[i];
            rest = rest - (i + 1);
        }
    }
    
    std::cout << smsNum << std::endl;

    return 0;
}