C公司今年大盈利,老板很高兴,奖励每个员工者m元。但老板又有点小心眼,他不想 让你那么痛快的掌到奖励,他举办了一场比赛,所有员工参加完比赛之后才决定你能拿多少 奖金! 接下来老板宣布比赛规侧: 比赛时间分为n个时段(n<=500),比赛又给出了很多小游戏,每个小游戏都必须在规定期限ti时间段内完成。如果一个游戏没能在规定时间段内完成,则要从奖励费m元中扣取一部分钱wi,wi为自然数,不同的游戏扣去的钱是不一样的。当然,每个游戏本身都很简单,保证每个参赛者都能在1个时段内完成,而且都必须从整时段开始。老板只是想考一考每个参赛者如何安排组织自己做游戏的顺序。作为一个非常努力上进的员工,小明很想赢得冠军,当然更想赢取最多的钱!那么他改怎么选择才能赢得最多的钱!注意:比赛绝对不会让参赛者赔钱。 【输入格式】 第一行为m,表示奖励的钱。 第二行为n,表示有n个小游戏。 第三行有n个数,分别表示游戏1到n的规定完成期限时间段ti。 第四行有个数,分别表示游戏1到n不能在规定期限时间段内完成的扣款数额wi。 【输出格式】 输出一行,表示小明能赢取最多的钱 【样例输入】 10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 【样例输出】 9950 数据说明 对于100%的数据,1≤n≤500,1≤m≤5×10^5,1≤ti≤n,1≤wi≤1000。
2条回答 默认 最新
- 阿里嘎多学长 2024-07-21 14:50关注
以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳:
这个问题可以通过贪心算法来解决。贪心算法在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的。在这个场景中,贪心算法将选择扣款数额最大的游戏先完成,因为这样可以在有限的时间段内减少未按时完成游戏的罚款。
以下是解决这个问题的C++代码示例:
#include <iostream> #include <vector> #include <algorithm> // 用于std::sort using namespace std; // 定义一个结构体来存储游戏的时间段和扣款数额 struct Game { int ti; int wi; }; int main() { int m, n; cin >> m >> n; // 读取每个游戏的时间段和扣款数额 vector<Game> games(n); for (int i = 0; i < n; ++i) { cin >> games[i].ti; } for (int i = 0; i < n; ++i) { cin >> games[i].wi; } // 根据扣款数额降序排序游戏 sort(games.begin(), games.end(), [](const Game &a, const Game &b) { return a.wi > b.wi; }); // 遍历排序后的游戏,安排完成时间 int time = 1; // 当前时间段 for (const auto &game : games) { if (time <= game.ti) { // 如果当前时间段小于等于游戏的截止时间,则安排在当前时间段完成 m -= game.wi; // 扣除罚款 time++; // 进入下一个时间段 } else { // 如果当前时间段已经超过了游戏的截止时间,则不扣款 // 因为题目保证每个游戏都能在1个时间段内完成 } } // 输出小明能赢取的最多奖金 cout << m << endl; return 0; }
这段代码首先定义了一个结构体
Game
来存储每个游戏的时间段和扣款数额。然后,它读取输入数据,并使用std::sort
函数根据扣款数额对游戏进行降序排序。接着,它遍历排序后的游戏列表,根据当前时间段和游戏的截止时间来决定是否需要扣除罚款。最后,它输出小明在最佳策略下能赢取的最多奖金。请注意,这段代码假设所有游戏都可以在1个时间段内完成,并且小明会尽可能地在每个时间段内完成游戏以避免罚款。如果有任何特殊情况或边界条件需要考虑,代码可能需要相应的调整。
解决 无用评论 打赏 举报 编辑记录
悬赏问题
- ¥15 osm下载到arcgis出错
- ¥15 Dell g15 每次打开eiq portal后3分钟内自动退出
- ¥200 使用python编写程序,采用socket方式获取网页实时刷新的数据,能定时print()出来就行。
- ¥15 matlab如何根据图片中的公式绘制e和v的曲线图
- ¥15 我想用Python(Django)+Vue搭建一个用户登录界面,但是在运行npm run serve时报错了如何解决?
- ¥15 QQ邮箱过期怎么恢复?
- ¥15 登录他人的vue项目显示服务器错误
- ¥15 (标签-android|关键词-app)
- ¥15 comsol仿真压阻传感器
- ¥15 Python线性规划函数optimize.linprog求解为整数