自动搬运

查看原文

来自洛谷，原作者为

	shixinyi **

搬运于2025-08-24 21:34:22，当前版本为作者最后更新于2017-11-03 09:03:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到楼上都是dp，我来发一个贪心的题解。

由于请小红吃饭的代价是 $Q \times x$ 。

所以如果请小红吃饭的总时间一定那么请小红吃饭的代价就是一定的。

我们考虑当请小红吃饭的天数是 $i$ ，那么需要旅游的总时间就是 $n-i$ ，旅游最多可以被吃饭分成 $i+1$ 次。

我们很容易可以证明每次旅游时间最平均的时候是最优的。

于是我们枚举请小红吃饭的总时间，然后计算旅游的最少代价。

这样时间复杂度为O(n)、空间复杂度为O(1)。

表示大常数选手贪心跑得比dp还要慢一些。

code:

//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
const int maxn=2e5+10;
const ll INF=1e17;
ll n,p,q,ans=INF;

ll trav(ll day,ll times) {
    ll x=day/times,y=day%times;
    return p*(times-y)*x*x+p*y*(x+1)*(x+1);//贪心，将除不尽多出的部分也平均分配
}

int main() {
    scanf("%lld%lld%lld",&n,&p,&q);
    for(int i=0;i<=n;++i) ans=min(ans,i*q+trav(n-i,i+1));//枚举请小红吃饭的总时间，计算最小的旅游代价
    printf("%lld",ans);
    return 0;
}