P6023 走路

2024-05-15 19:52

文章标签 走路 p6023

本文主要是介绍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$ 。

贪心思路:

首先想一想,不管如何奖励,奖励所得都是1分,所以不必纠结权重了,那么该如何分配步数呢,只需看奖励的时间了,因为奖励是累加的,由于每天在遇到奖励的时候需要一开始就走一段路,所以如果中间更换天数的时候那么必须浪费的可能,据此分析,如果要让收益最大,那么这些步数一定是分布在同一天的

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#define int long long 
using namespace std;
int g[1000005];//记录每一天的奖励
int sum, mmax;
int n, m, k, m1,a,b;
signed main()
{cin >> n >> m >> k;for (int i = 0; i < k; i++){cin >> a >> b;if (n > b)//一定是严格大于,因为标号从0开始{g[a] += n-b;//该天该段的奖励}}for (int i = 1; i <= m; i++)mmax = max(mmax, g[i]);//取最大cout << mmax << endl;return 0;
}