[LeetCode] 1954. Minimum Garden Perimeter to Collect Enough Apples

3778 ワード

https://leetcode.com/contest/weekly-contest-252/problems/minimum-garden-perimeter-to-collect-enough-apples/
Constraints:
  • 1 <= neededApples <= 10^15
  • =>数学式を書くだけで時間の複雑さを減らすことができます.
    等差数列の和n(n+1)/2 n(n+1)/2 n(n+1)/2 n(n+1)/2を用いた.
    [python]
    def minimumPerimeter(self, neededApples: int) -> int:
        n = 0
        while(n * (n + 1) * (2*n + 1) * 2 < neededApples):
            n += 1
        return n * 8
    [C++]
    long long minimumPerimeter(long long neededApples) {
        long n = 0;
        while(n * (n + 1) * (2 * n + 1) * 2 < neededApples)
            n++;
    
        return n * 8;
    };

  • 同じ公式で同じ原理で解くと、PythonとC++Runtimeの違いは何ですか?スピードはCはヤクザ.

  • 暴力的な方法で簡単に解くことができますが、減速したいならビンリーで検索できます.