云短信平台优惠活动
题目描述
代码语言：javascript
复制题目描述：
某云短信运营商，为庆祝国庆，推出充值优惠活动。现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
输入描述：第一行客户预算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
知识点：哈希表、队列、数组、统计、贪心
C 代码实现
代码语言：javascript
复制#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;
}
