时间轴

2025-11-12

init

题目：

P2654 使数组所有元素变成 1 的最少操作次数

https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/description/?envType=daily-question&envId=2025-11-12

只要有一个 1，就能扩散其他非 1 的数字变成 1，所以我们的目标就是找出 1 或能变成 1 的子数组。

  1. 情况 1：数组中已经有 1
  2. 情况 2：没有 1，我们要找出 最短子数组使得其所有数的 gcd = 1，记长度为 len。只要能在那段中通过操作造出一个 1，然后再传播到全数组需要 n - 1 次操作。那么答案 = len - 1 + (n - 1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <vector>
#include <numeric>
#include <algorithm>
#include <climits>
using std::vector;

class Solution {
    public:
	int minOperations(vector<int> &nums)
	{
		int n = nums.size();
		int cnt1 = 0;
		for (int x : nums) {
			if (x == 1) {
				cnt1++;
			}
		}

		// 情况1：数组中已经有1
		if (cnt1 > 0) {
			return n - cnt1;
		}

		// 情况2：没有1，找最短gcd为1的子数组
		// 我们要找出 最短子数组 gcd = 1 的长度为 len。
		// 只要能在那段中通过操作造出一个 1，然后再传播到全数组需要 n - 1 次操作。
		// 答案 = len - 1 + (n - 1)。
		int ans = INT_MAX;
		int g;
		for (int i = 0; i < n; i++) {
			g = nums[i];
			for (int j = i + 1; j < n; j++) {
				g = std::gcd(g, nums[j]);
				if (g == 1) {
				        // j-i+1为gcd为1的子数组长度
					ans = std::min(ans, j - i + 1);
					break;
				}
			}
		}

		if (ans == INT_MAX) {
			return -1; // 不可能造出1
		}
		return (ans - 1) + (n - 1); // 造出一个1，再扩散成全1
	}
};