当前位置：首页 > ai >正文

【C++贪心】P6023 走路|普及

ai 2025/5/3 5:11:43

本文涉及知识点

C++贪心

P6023 走路

题目背景

小 W 下载了一款运动软件。

题目描述

小 W 准备在接下来的 $m$ 天中锻炼，由于他不能走得太多以至于累死（怎么可能呢），所以他这 $m$ 天最多一共只能走 $n$ 步。
这个运动软件为了激励小 W 走路，推出了 $k$ 种激励措施，每种激励措施都形如“如果你第 $p$ 天中走完了 $q$ 步，那么第 $p$ 天中接下来的每一步都会给你加 $1$ 积分”。激励措施可以叠加，即走一步你可能可以获得多于 $1$ 积分。
现在小 W 想知道，他总计最多可以获取多少积分呢？

输入格式

第一行三个整数 $n, m, k$ ，意义如上。
接下来 $k$ 行，每行两个整数 $p, q$ ，表示一个激励措施，意义如上。

输出格式

一行 $1$ 个整数，表示 $m$ 天后最多可以获得的积分。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释：
只有一种方案，即在第一天走 $5$ 步，第一、二步各获得 $1$ 积分，第三、四步各获得 $2$ 积分，第五步获得 $3$ 积分，总计 $9$ 积分。

数据范围：
对于 $10\%$ 的数据， $n,m,k\le10$ 。
对于 $40\%$ 的数据， $\le 10^3$ 。
对于 $100\%$ 的数据， $1\le n\le 10^{12}$ ， $1\le m,k\le 10^5$ ， $1\le p\le m$ ， $0\le q\le n$ 。

贪心

性质一：一定只有一天跑步，其它时间休息。不失一般性，假定第一天，最后一步的积分为n1，第二天最后一步积分为n2。不妨令n1 >=n2。将第二天步数，全部改到第一天，则这些步数每步都有n1积分。
v[i]记录第天所有奖励要求，如果>=n忽略。
枚举第i天跑完n步。 i $[1,m]
此天的奖励为：n*v.size()- $\sum$ v[i]

代码

核心代码

class Solution {
public:long long MaxS(long long n, int M, vector<pair<int, long long>>& scorce) {vector<vector<long long>> v(M + 1);for (const auto& [p, q] : scorce) {if (q >= n) { continue; }v[p].emplace_back(q);}long long ans = 0;for (int m = 1; m <= M; m++) {long long sub = accumulate(v[m].begin(), v[m].end(), 0LL);ans = max(ans, n * (long long)v[m].size() - sub);}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGlong long n;int m, k;scanf("%lld%d%d", &n,&m,&k);vector<pair<int, long long>> score;while (k--) {int d1;long long d2;scanf("%d%lld", &d1, &d2);score.emplace_back(make_pair(d1, d2));}//Out(score);auto res = Solution().MaxS(n, m, score);printf("%lld", res);return 0;
}

单元测试

public:TEST_METHOD(TestMethod11){scorce = { {1,0},{1,2},{1,4} };auto res = Solution().MaxS(5, 1, scorce);AssertEx(9LL, res);}TEST_METHOD(TestMethod12){scorce.assign(100'000, make_pair(1, (long long)1e11));auto res = Solution().MaxS((long long)1e12, 2, scorce);AssertEx(90000000000000000LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功