自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:16:37，当前版本为作者最后更新于2020-01-14 19:49:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 走路

一句话：贪心即可。

假如有两天，比如第一天和第二天都走了路，设两天走的步数、已获得积分、接下来每步获得的积分分别为 $a_1,a_2,b_1,b_2,c_1,c_2$，不妨设 $c_1\ge c_2$。

如果我们把所有步数都放到第一天，那么我们至少会获得 $b_1+a_2\times c_1$ 分（后面可能还有其他的激励措施）。同时，由于同一天内每一步获得的分数是递增（非严格）的，我们有

所以，如果分数最大，那么必定所有步数都是放在同一天。这样不是更容易猝死了吗

于是，我们对于每天计算一下如果这天走完所有步可以得到多少积分（直接读入时累加即可），然后取个最大的即可。

$\texttt{code}:$

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

ll a[100005];
ll n,m,k,mx=0;
int main()
{
	rd(n);rd(m);rd(k);
	F(i,1,k) {ll p=rd();ll q=rd();a[p]+=n-q;}
	F(i,1,m) if(a[i]>=a[mx]) mx=i;
	cout<<a[mx]<<endl;
	return 0;
}