解题思路

• 核心目标：通过若干次“把某个数 ai 拆成两个正整数相加”的操作，使数组满足 max(a) ≤ 2 × min(a)。

• 关键观察：

  • 拆分会让元素变小，但不能让当前最小值变小，否则条件更难满足。因此最优策略是不拆分最小值，并在拆分其他元素时尽量让拆出的每一段都 ≥ 最小值 m。
  • 若数组最小值为 m，只要把每个元素 ai 拆成若干段，使每段都 ≤ 2m 且 ≥ m，就能保证最终整体满足条件，同时不降低 m。

• 化为计数问题：

  • 要把 ai 切成 p 段，使每段的最大值 ceil(ai / p) ≤ 2m，则最小可行段数为 p_min = max(1, ceil(ai / (2m)))。
  • 需要的操作次数是把一个数分成 p 段需 p-1 次，因此对该 ai 的最少操作是 max(0, ceil(ai / (2m)) - 1)。

• 算法：

  1. 扫一遍求最小值 m。
  2. 对每个 ai 累加 max(0, ceil(ai / (2m)) - 1)。
  3. 总和即答案。

• 实现要点：

  • 使用整除上取整：ceil(x / y) = (x + y - 1) // y。
  • 全程用 64 位整型避免溢出（Java long、C++ long long）。

复杂度分析

• 时间复杂度：O(n)，一次扫描求最小值，再一次扫描累加。
• 空间复杂度：O(1)（不计输入存储）。

代码实现

Python

# 题面功能在外部函数里，主函数只做输入输出
import sys

def min_operations_to_pleasant(arr):
    # 计算使数组满足 max <= 2*min 的最少拆分次数
    m = min(arr)
    twice = 2 * m
    ans = 0
    for a in arr:
        # 对每个元素累加 max(0, ceil(a/(2m)) - 1)
        need = (a + twice - 1) // twice  # ceil(a / (2m))
        if need > 1:
            ans += need - 1
    return ans

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    arr = list(map(int, data[1:1+n]))
    print(min_operations_to_pleasant(arr))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名统一为 Main
import java.io.*;
import java.util.*;

public class Main {
    // 外部函数：计算最少拆分次数
    public static long minOperationsToPleasant(long[] arr) {
        long m = Long.MAX_VALUE;
        for (long v : arr) m = Math.min(m, v);  // 最小值
        long twice = 2L * m;
        long ans = 0;
        for (long a : arr) {
            // 需要的段数 need = ceil(a / (2m))
            long need = (a + twice - 1) / twice;
            if (need > 1) ans += need - 1;     // 累加操作次数
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 数据范围较大但行数少，默认输入方式即可
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        while (s1 != null && s1.trim().isEmpty()) s1 = br.readLine();
        int n = Integer.parseInt(s1.trim());
        String[] parts = br.readLine().trim().split("\\s+"); // 用空白分割
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) arr[i] = Long.parseLong(parts[i]);
        System.out.println(minOperationsToPleasant(arr));
    }
}

C++

// ACM 风格：主函数读写，功能写在外部函数
#include <bits/stdc++.h>
using namespace std;

// 计算最少拆分次数
long long minOperationsToPleasant(const vector<long long>& a) {
    long long m = *min_element(a.begin(), a.end()); // 最小值
    long long twice = 2LL * m;
    long long ans = 0;
    for (long long x : a) {
        // need = ceil(x / (2m)) = (x + 2m - 1) // (2m)
        long long need = (x + twice - 1) / twice;
        if (need > 1) ans += need - 1; // 每个元素增加的操作次数
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << minOperationsToPleasant(a) << "\n";
    return 0;
}

题目内容

在游戏中，主人公 $Tk$有一个长度为{$a_1,a_2,...,a_n$}的数组 ； 他将一个数组称为令人心动，当且仅当该数组的最大值不超过最小值的两倍，即$max(a_1,...,a_n)≤2×min(a_1,...,a_n)$； 为了让自己的数组变为令人心动，他可以进行以下操作多次，直到满足条件：

• 选择一个元素$a_i$，并选取两个正整数 $x,y$满足$x+y=a_i$ ，将$a_i$删除，并将$x,y$插入数组中； 请你计算使数组变为令人心动所需的最少操作次数。

输入描述

第一行输入一个整数$n(1≤n≤2×10^5)$，表示数组的长度； 第二行输入$n$个整数$a_1,a_2,...,a_n(1≤a_i≤10^9)$，表示数组中的元素。

输出描述

输出一个整数，表示将数组变为令人心动的最少操作次数。

样例1

输入

3
3 6 13

输出

2

说明

• 说明 在此样例中，初始数组为 {$3,6,13$}，操作方案不唯一；
• 将 $13$ 拆分为$5$ 和$8$，数组变为{$3,6,5,8$} ；
• 将 $8$ 拆分为 $4$和$4$，数组变为{$3,6,5,4,4$} ，此时最大值 $6$ 不超过最小值 $3$ 的两倍，满足条件，共需 $2$次操作。