滑窗|镜像复用

lc3413

镜像翻转 复用代码

先排序硬币区间，用滑动窗口算正向最大硬币数

再反转并转换区间方向二次计算，最终取两次结果的最大值。

#include <vector>

#include <algorithm>

using namespace std;

class Solution {

using ll = long long;

ll f(vector<vector<int>>& t, int l) {

ll a = 0, s = 0;

int i = 0;

for (auto& v : t) {

int L = v[0], R = v[1], c = v[2];

s += (ll)(R - L + 1) * c;

int cl = R - l + 1;

while (t[i][1] < cl) {//find ok_l

s -= (ll)(t[i][1] - t[i][0] + 1) * t[i][2];

i++;

}

ll u = max((ll)(cl - t[i][0]) * t[i][2], 0LL);

a = max(a, s - u);

}

return a;

}

public:

ll maximumCoins(vector<vector<int>>& c, int k) {

sort(c.begin(), c.end());

ll a = f(c, k);

reverse(c.begin(), c.end());

for (auto& v : c) {

int tmp = v[0];

v[0] = -v[1];

v[1] = -tmp;

}

returnmax(a, f(c, k));

}

};