时间轴

2025-11-13

init

题目：

P3228 将 1 移动到末尾的最大操作次数

https://leetcode.cn/problems/maximum-number-of-operations-to-move-ones-to-the-end/description/?envType=daily-question&envId=2025-11-13

最大操作次数，那么就从左边的 1 开始，把相邻的 1 看成 1 组，它们由一个或多个相邻的 0 分割，假设由 n 组 1，那么不难看出第 i 组 1 移动到最后一组 1 需要的操作次数为：第 i 组 1 的 1 的个数*(n-i)

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
#include <string>
#include <vector>
using std::string;
using std::vector;

class Solution {
    public:
	int maxOperations(string s)
	{
		int i, n = s.size();
		int max_ops = 0;

		int last_1_pos;
		vector<int> vec;
		for (i = 0; i < n; i++) {
			if (s[i] == '1') {
				last_1_pos = i;
				break;
			}
		}
		while (i < n) {
			while (i < n && s[i] == '1') {
				i++;
			}

			vec.push_back(i - last_1_pos);

			while (i < n && s[i] == '0') {
				i++;
			}
			last_1_pos = i;
		}
		if (s.back() == '1' && !vec.empty()) {
			vec.pop_back();
		}
		n = vec.size();
		for (i = 0; i < n; i++) {
			max_ops += vec[i] * (n - i);
		}
		return max_ops;
	}
};