村长的雪糕

本题考察二分答案

思路

这题第一眼很容易想到暴力模拟，枚举出买多少根雪糕，枚举到最小能吃到 $n$ 个雪糕的个数是多少。但是看一眼数据范围，$10^5 \times 10^{12} = 10^{17}$ 明显是大于我们暴力 $O(n)$ 的最大范围（$10^8$）的。考虑使用更第时间复杂度如 $O(logn)$ 的算法。我们知道，二分答案的时间复杂度是 $O(logn * f(n))$ ，这里的 $f(n)$ 是 check 函数的时间复杂度。根据题意，check 函数应为判断买 $mid$ 个雪糕能否完成任务，采用模拟算法来实现的话，时间复杂度是 $O(log_3{mid})$ 。最终的时间复杂度为 $O(logn)$ 可以满足数据范围。

C++朴素实现

#include <bits/stdc++.h>
using namespace std;
int64_t n;
bool check(int64_t mid) {
    auto res = mid;
    while (mid >= 3) {
        auto t = mid / 3;
        res += t;
        mid -= t << 1;
    }
    return res < n;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n) {
        int64_t l = 0, r = 1e12 + 5;
        while (l < r) {
            auto mid = (l + r) >> 1;
            if(check(mid))
                l = mid + 1;
            else
                r = mid;
        }
        cout << l << endl;
    }
    return 0;
}

C++ STL实现

需要注意的是，你需要打开 O2 优化

#include <bits/stdc++.h>
using namespace std;
constexpr int64_t maxn = 1e12 + 1;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64_t n;
    auto &&answer_range = views::iota(0ll, maxn);
    auto check = [&](auto mid) {
        auto res = mid;
        while (mid >= 3) {
            auto t = mid / 3;
            res += t;
            mid -= t << 1;
        }
        return res < n;
    };
    while (cin >> n)
        cout << *ranges::partition_point(answer_range, check) << endl;
    return 0;
}

Python 实现

from sys import stdin
input = stdin.readline
n = 0

def check(mid):
    global n
    res = mid
    while mid >= 3:
        t = mid // 3
        res += t
        mid -= t << 1
    return res < n

while True:
    try:
        n = int(input())
        l, r = 0, 10 ** 12 + 5
        while l < r:
            mid = (l + r) >> 1
            if check(mid):
                l = mid + 1
            else:
                r = mid
        print(l)
    except:
        break

Java 实现

import java.util.*;
import java.util.function.*;

public class Main {
    private static final Scanner scanner = new Scanner(System.in);

    public static void solve() {
        var n = scanner.nextLong();
        LongFunction<Boolean> check = (long mid) -> {
            var res = mid;
            while (mid >= 3) {
                var t = mid / 3;
                res += t;
                mid -= t << 1;
            }
            return res < n;
        };
        long l = 0, r = (long) (1e12 + 1);
        while(l < r) {
            var mid = (l + r) >> 1;
            if(check.apply(mid))
                l = mid + 1;
            else
                r = mid;
        }
        System.out.println(l);
    }

    public static void main(String[] args) {
        while (scanner.hasNext())
            solve();
        scanner.close();
    }
}