3507. Minimum Pair Removal to Sort Array I
Given an array nums, you can perform the following operation any number of times:
- Select the adjacent pair with the minimum sum in
nums. If multiple such pairs exist, choose the leftmost one.
- Replace the pair with their sum.
Return the minimum number of operations needed to make the array non-decreasing.
An array is said to be non-decreasing if each element is greater than or equal to its previous element (if it exists).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
bool nok(vector<int>& A) {
for(int i = 0; i < A.size() - 1; i++) {
if(A[i] > A[i+1]) return true;
}
return false;
}
public:
int minimumPairRemoval(vector<int>& nums) {
int res = 0;
while(nok(nums)) {
int best = 0;
for(int i = 1; i < nums.size() - 1; i++) {
if(nums[i] + nums[i+1] < nums[best] + nums[best+1]) best = i;
}
nums[best] += nums[best+1];
for(int i = best + 1; i < nums.size() - 1; i++) nums[i] = nums[i+1];
nums.pop_back();
res++;
}
return res;
}
};
|
