题解 | #分贝壳#

#include <iostream>
using namespace std;
typedef unsigned long long ULL;

// 模拟分配过程
void simulate(ULL &n, ULL &n1, ULL &n2, const ULL &m) {
    while (n > 0) {
        // 妞妞取贝壳
        ULL m1 = min(n, m);
        n1 += m1;
        n -= m1;
        
        // 牛牛取贝壳
        ULL m2 = n;
        n2 += m2 / 10;
        n -= m2 / 10;
    }
}

// 精确查找
void findExact(const ULL &total, ULL &m) {
    while (true) {
        ULL n = total;
        ULL n1 = 0, n2 = 0;
        simulate(n, n1, n2, m);
        if (n1 >= n2) return;
        ++m;
    }
}

int main() {
    ULL total;
    cin >> total;
    
    // 二分查找
    ULL left = 0, right = total;
    while (true) {
        ULL m = (left + right) / 2;
        ULL n = total;
        ULL n1 = 0, n2 = 0;
        
        simulate(n, n1, n2, m);
        
        if (m - left <= 2) {
            findExact(total, m);
            cout << m << endl;
            break;
        }
        
        if (n1 > n2) right = m;
        else left = m;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    static class Solution {
        // 模拟分配过程
        void simulate(long[] state, long m) {
            while (state[0] > 0) {
                // 妞妞取贝壳
                long m1 = Math.min(state[0], m);
                state[1] += m1;
                state[0] -= m1;
                
                // 牛牛取贝壳
                long m2 = state[0];
                state[2] += m2 / 10;
                state[0] -= m2 / 10;
            }
        }
        
        // 精确查找
        void findExact(long total, long[] m) {
            while (true) {
                long[] state = {total, 0, 0}; // n, n1, n2
                simulate(state, m[0]);
                if (state[1] >= state[2]) return;
                ++m[0];
            }
        }
        
        public long solve(long total) {
            long left = 0, right = total;
            long[] m = {0};
            
            while (true) {
                m[0] = (left + right) / 2;
                long[] state = {total, 0, 0}; // n, n1, n2
                
                simulate(state, m[0]);
                
                if (m[0] - left <= 2) {
                    findExact(total, m);
                    return m[0];
                }
                
                if (state[1] > state[2]) right = m[0];
                else left = m[0];
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        Solution solution = new Solution();
        System.out.println(solution.solve(n));
    }
}

def simulate(n, m):
    """模拟分配过程"""
    n1 = n2 = 0
    while n > 0:
        # 妞妞取贝壳
        m1 = min(n, m)
        n1 += m1
        n -= m1
        
        # 牛牛取贝壳
        m2 = n
        n2 += m2 // 10
        n -= m2 // 10
    return n1, n2

def find_exact(total, m):
    """精确查找"""
    while True:
        n1, n2 = simulate(total, m)
        if n1 >= n2:
            return m
        m += 1

def solve(total):
    """二分查找解决方案"""
    left, right = 0, total
    
    while True:
        m = (left + right) // 2
        n1, n2 = simulate(total, m)
        
        if m - left <= 2:
            return find_exact(total, m)
        
        if n1 > n2:
            right = m
        else:
            left = m

if __name__ == "__main__":
    n = int(input())
    print(solve(n))