Sengxian's Blog

题目地址

描述

求 $X \in [1, m](1\le m\le 10^{15})$，满足 $\mathrm{pair}(f(X), X)$ 最大。
$f(X)$ 是递归定义的：找到最大满足 $a^3 \le X$ 的 $a$，则 $f(X) = f(X - a ^ 3) + 1$，边界 $f(0) = 0$。

分析

我们的思路是先来考虑最大的 $f(X)$，再根据这个值构造出最大的一个 $X$。
假设 step(m) 能求出最大的 $f(X), X\in [1, m]$，我们来考虑怎么转移。设 $a$ 是最大的满足 $a^3 \le m$ 的数。则我们要么选 $a^3$，要么选 ${(a-1)}^3$，证明如下：

1. 选 $a^3$，则 $\mathrm{step}(m) = \mathrm{step}(m - a^3) + 1$。
2. 选 ${(a-1)}^3$，则 $\mathrm{step}(m) = \mathrm{step}(a^3 - 1 - {(a-1)}^3) + 1$。
3. 选 ${(a-2)}^3$，则 $\mathrm{step}(m) = \mathrm{step}({(a-1)}^3 - 1 - {(a-2)}^3) + 1$。

解释下第二个，由于选 ${(a-1)}^3$，所以 $X$ 不能大于等于 $a^3$，否则根据题目要求就必须选 $a^3$，根据贪心让 $X = a^3 - 1$。
可以发现 $\mathrm{step}(m)$ 是单调不减的，所以我们应该取 $\max(m - a^3, a^3 - 1 - {(a-1)}^3, {(a-1)}^3 - 1 - {(a-2)}^3)$，明显有 $a^3 - 1 - {(a-1)}^3 \ge {(a-1)}^3 - 1 - {(a-2)}^3$，所以我们在 1, 2 中间选一个较大的递归下去。

这样我们就可以求出 step(m) 了，接着考虑求最大值。根据刚才的分析，若当前的上限是 $m$，则必定要选 $a^3$ 或 ${(a-1)}^3$，如果选 $a^3$ 能达到最优值的话，就选 $a^3$，否则我们选 ${(a-1)}^3$。

我一开始对 “如果选 $a^3$ 能达到最优值的话，就选 $a^3$，否则我们选 ${(a-1)}^3$” 有疑问，有没有可能尽管 $a^3$ 达到最优值，选 ${(a-1)}^3$ 仍然更优呢？
可以发现，选 $a^3$ 的话，我们求出的答案必定大于等于 $a^3$，而选 ${(a-1)}^3$，意味着我们的 $X$ 不能超过 $a^3 - 1$，所以答案是小于等于 $a^3 - 1$ 的，所以能选 $a^3$ 时就选 $a^3$。

代码

//  Created by Sengxian on 6/9/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 679B 贪心
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxa = 1000000 + 3;
ll cube[maxa];

inline ll get(ll m) {
    ll l = 1, r = min(maxa, (int)sqrt(m) + 1);
    while (r - l > 1) {
        ll mid = (l + r) >> 1;
        if (cube[mid] <= m) l = mid;
        else r = mid;
    }
    return l;
}

ll step(ll m) {
    if (m <= 7) return m;
    ll a = get(m); //无需讨论选几个 a ^ 3
    return 1 + step(max(m - cube[a], cube[a] - 1 - cube[a - 1]));
}

int main() {
    for (ll i = 0; i < maxa; ++i) cube[i] = i * i * i;
    ll m, ans = 0;
    cin >> m;
    //贪心，得到最大的
    while (m) {
        if (m <= 7) {ans += m; break;}
        ll a = get(m);
        //如果选 a ^ 3 可以得到最优解，则选。
        if (step(m) == 1 + step(m - cube[a])) m -= cube[a], ans += cube[a];
        else m = cube[a] - 1 - cube[a - 1], ans += cube[a - 1];
    }
    cout << step(ans) << ' ' << ans << endl;
    return 0;
}