思路

如果数组长度小于或等于2，操作次数就是数组长度，其余情况是前两次操作会染两个，第三次操作开始，为了最小化操作次数，则需要每次操作染色尽可能多，所有如果当前有x个染色块，则最多可以新增染色x-1个，所有每次贪心染色x-1个，直到全部染色完。

代码

python

t=int(input())
for i in range(t):
    n=int(input())
    if n<=2:
        print(n)
        continue
    x,cnt=2,2
    while x<n:
        x+=x-1
        cnt+=1
    print(cnt)

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int t = scanner.nextInt();
        
        for (int i = 0; i < t; i++) {
            long n = scanner.nextLong();
            
            if (n <= 2) {
                System.out.println(n);
                continue;
            }
            
            long x = 2, count = 2;
            while (x < n) {
                x += x - 1;
                count++;
            }
            
            System.out.println(count);
        }
    }
}

c++

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    for (int i = 0; i < t; i++) {
        long long n;
        cin >> n;
        
        if (n <= 2) {
            cout << n << endl;
            continue;
        }
        
        long long x = 2, count = 2;
        while (x < n) {
            x += x - 1;
            count++;
        }
        
        cout << count << endl;
    }
    
    return 0;
}

题目内容

小美正在对一个长度为n的数组a进行染色。初始时所有元素均为无色。他每次可以选择以下操作之一：

• 选择一个索引将其染成红色。

• 选择一个区间[$l,r$]，如果该区间内红色元素的个数多于无色元素的个数，则将这个区间内的所有元素全部染成红色。

  小美至少需要多少次操作，才能将整个数组全部染成红色？

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤10^5$)代表数据组数，每组测试数据描述如下: 在一行上输入一个整数$n$($1≤n≤10^9$)代表数组中的元素数量。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表将整个数组全部染成红色所需的最少操作次数。

样例1

输入

3
3
4
12

输出

3
4
6