2593. Find Score of an Array After Marking All Elements
You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:
- Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
- Add the value of the chosen integer to score.
- Mark the chosen element and its two adjacent elements if they exist.
- Repeat until all the array elements are marked.
Return the score you get after applying the above algorithm.
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
| class Solution {
public:
long long findScore(vector<int>& nums) {
long long res = 0;
vector<int> mark(nums.size());
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q, exc;
for(int i = 0; i < nums.size(); i++) q.push({nums[i], i});
while(q.size()) {
auto [x, idx] = q.top(); q.pop();
mark[idx] = true;
res += x;
if(idx - 1 >= 0 and !mark[idx-1]) {
mark[idx-1] = true;
exc.push({nums[idx-1], idx-1});
}
if(idx + 1 < nums.size() and !mark[idx+1]) {
mark[idx+1] = true;
exc.push({nums[idx+1], idx+1});
}
while(exc.size() and exc.top() == q.top()) {
exc.pop();
q.pop();
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
long long findScore(vector<int>& nums) {
long long res = 0;
vector<int> mark(nums.size());
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
for(int i = 0; i < nums.size(); i++) q.push({nums[i], i});
while(q.size()) {
while(q.size() and mark[q.top().second]) q.pop();
if(q.empty()) break;
auto [x, idx] = q.top(); q.pop();
mark[idx] = true;
res += x;
if(idx - 1 >= 0) mark[idx-1] = true;
if(idx + 1 < nums.size()) mark[idx+1] = true;
}
return res;
}
};
|
