本文涉及知识点
C++贪心
P6023 走路
题目背景
小 W 下载了一款运动软件。
题目描述
小 W 准备在接下来的
m
m
m 天中锻炼，由于他不能走得太多以至于累死（怎么可能呢），所以他这
m
m
m 天最多一共只能走
n
n
n 步。
这个运动软件为了激励小 W 走路，推出了
k
k
k 种激励措施，每种激励措施都形如“如果你第
p
p
p 天中走完了
q
q
q 步，那么第
p
p
p 天中接下来的每一步都会给你加
1
1
1 积分”。激励措施可以叠加，即走一步你可能可以获得多于
1
1
1 积分。
现在小 W 想知道，他总计最多可以获取多少积分呢？
输入格式
第一行三个整数
n
,
m
,
k
n,m,k
n,m,k，意义如上。
接下来
k
k
k 行，每行两个整数
p
,
q
p,q
p,q，表示一个激励措施，意义如上。
输出格式
一行 1 1 1 个整数，表示 m m m 天后最多可以获得的积分。
样例 #1
样例输入 #1
5 1 3
1 0
1 2
1 4
样例输出 #1
9
提示
样例解释：
只有一种方案，即在第一天走
5
5
5 步，第一、二步各获得
1
1
1 积分，第三、四步各获得
2
2
2 积分，第五步获得
3
3
3 积分，总计
9
9
9 积分。
数据范围：
对于
10
%
10\%
10% 的数据，
n
,
m
,
k
≤
10
n,m,k\le10
n,m,k≤10。
对于
40
%
40\%
40% 的数据，
n
,
m
,
k
≤
1
0
3
n,m,k \le 10^3
n,m,k≤103。
对于
100
%
100\%
100% 的数据，
1
≤
n
≤
1
0
12
1\le n\le 10^{12}
1≤n≤1012，
1
≤
m
,
k
≤
1
0
5
1\le m,k\le 10^5
1≤m,k≤105，
1
≤
p
≤
m
1\le p\le m
1≤p≤m，
0
≤
q
≤
n
0\le q\le n
0≤q≤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 _DEBUG
freopen("a.in", "r", stdin);
#endif // DEBUG
long 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);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
发布评论