→ sixB: 好羨慕oin這麼厲害一直上分 01/24 06:05
→ sixB: 我要是這禮拜有打的話 看到這題直接掛在那邊晃來晃去qwq 01/24 06:05
→ DJYOMIYAHINA: 我好爛 01/24 08:42
3430.
Q4.
剛剛洗澡洗一洗突然想到怎麼寫
用了一個像是KMP的怪方法
對每個數找左右range
原本以為這一步是關鍵
寫出來之後在count個數那邊卡了好久==
range都查完了
被關太久了
怎麼連數數都不會哇啊啊啊啊
去你媽的城市海巡數數仔
終於出來了2020
勾手指算的都是對的
寫成式子就一直錯嗚嗚嗚嗚
後面還是拆開來分開加
後來看別人寫的都好乾淨漂亮
什麼deque monostack 我都不會
我就這樣了
感覺20天好像也是一下就過了
https://i.imgur.com/NlXcxaU.jpeg
using ll = long long;
class Solution {
public:
long long minMaxSubarraySum(vector<int>& nums, int k) {
int n = nums.size();
ll res = 0;
// 1 3 5 4 6 7 2 8, k = 4
vector<pair<int, int>> mi_range(n), mx_range(n);
for(int i = 0; i < n; i++){
mi_range[i] = {i, i};
mx_range[i] = {i, i};
}
// [limit, rimit]
// if same value, choose small idx
// left to right, min range
for(int i = 1; i < n; i++){
int limit = i - k + 1;
int pos = i;
while(limit <= (pos-1) and 0 <= (pos-1) and nums[pos-1] > nums[i]){
pos = mi_range[pos-1].first;
}
mi_range[i].first = max(pos, limit);
}
// right to left, min range
for(int i = n-2; i >= 0; i--){
int rimit = i + k - 1;
int pos = i;
while((pos+1) <= rimit and (pos+1) < n and nums[i] <= nums[pos+1]){
pos = mi_range[pos+1].second;
}
mi_range[i].second = min(pos, rimit);
}
// left to right, max range
for(int i = 1; i < n; i++){
int limit = i - k + 1;
int pos = i;
while(limit <= (pos-1) and 0 <= (pos-1) and nums[pos-1] < nums[i]){
pos = mx_range[pos-1].first;
}
mx_range[i].first = max(pos, limit);
}
// right to left, max range
for(int i = n-2; i >= 0; i--){
int rimit = i + k - 1;
int pos = i;
while((pos+1) <= rimit and (pos+1) < n and nums[i] >= nums[pos+1]){
pos = mx_range[pos+1].second;
}
mx_range[i].second = min(pos, rimit);
}
/*
for(int i = 0; i < n; i++){
cout << i << "* " << nums[i] << ": ";
auto& [l, r] = mi_range[i];
cout << l << ' ' << r << ", ";
auto& [x, y] = mx_range[i];
cout << x << ' ' << y << "\n";
}
*/
auto cnt = [&](int i){
ll res = 0;
// cnt min
ll l = mi_range[i].first, r = mi_range[i].second;
ll len = r - l + 1;
l = i - l + 1;
r = r - i + 1;
if(l > r) swap(l,r);
// l <= r
// 1+2+...+l
ll r1 = (l+1) * l / 2;
r1 += l * (r - l);
r1 += (1+len-r) * (len-r) / 2;
if(len >= k){
r1 -= (1+len-k) * (len-k) / 2;
}
//cout << r1 << " ";
res += r1;
// cnt max
l = mx_range[i].first; r = mx_range[i].second;
len = r - l + 1;
l = i - l + 1;
r = r - i + 1;
if(l > r) swap(l,r);
// l <= r
// 1+2+...+l
ll r2 = (l+1) * l / 2;
r2 += l * (r - l);
r2 += (1+len-r) * (len-r) / 2;
if(len >= k){
r2 -= (1+len-k) * (len-k) / 2;
}
//cout << r2 << "\n";
res += r2;
return res;
};
for(int i = 0; i < n; i++){
//cout << i << " " << nums[i] << ": " ;
res += cnt(i) * nums[i];
}
return res;
}
};
--
很姆的咪
姆之咪
http://i.imgur.com/5sw7QOj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737669894.A.B19.html