差分+扫描线|

lc1851

有点像双指针的意思

class Solution {
public:
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
int n = intervals.size(), m = queries.size();
sort(intervals.begin(), intervals.end());
using pii = pair<int, int>;
vector<pii> qs;
for (int i = 0; i < m; ++i) {
qs.emplace_back(queries[i], i);
}
sort(qs.begin(), qs.end());
vector<int> ans(m, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq;
int i = 0;
for (auto& [x, j] : qs) {
while (i < n && intervals[i][0] <= x) {
int a = intervals[i][0], b = intervals[i][1];
pq.emplace(b - a + 1, b);
++i;
}
while (!pq.empty() && pq.top().second < x) {
pq.pop();
}
if (!pq.empty()) {
ans[j] = pq.top().first;
}
}
return ans;
}
};

lc1674

差分➕扫描线

差分统计数组两两配对和的不同区间所需移动次数，遍历求最小移动次数

sum：差分在“全需 2 次移动”的基准上，按区间调整真实移动次数。

class Solution {
public:
int minMoves(vector<int>& a, int l) {
int n = a.size();
vector<int> d(l * 2 + 2);
for (int i = 0; i < n / 2; ++i) {
int x = a[i], y = a[n - i - 1];
int lo = 1 + min(x, y);
int hi = l + max(x, y);
int s = x + y;
d[lo]--;
d[s]--;
d[s + 1]++;
d[hi + 1]++;

//对可抵达的结果 差分
}

int c = n,res = n;
for (int i = 2; i <= l * 2; ++i) {

//差分求和 得到可抵达点的操作数
c += d[i];
res = min(res, c);
}
return res;
}
};

1. 初始基准值 c = n

假设每个数字都要移动一次，数组长度为n

2. 差分的基准逻辑

差分数组的作用是修正这个基准值：

- 落在 [lo, sum) 区间的目标和，数对只需 1 次移动 → 总次数减 1，对应 d[lo]-- 。

- 目标和等于 sum 时，数对无需移动 → 总次数再减 1，对应 d[sum]-- 。

- 超过 sum 或 hi 后，修正失效，对应 d[sum+1]++ 和 d[hi+1]++ 把次数加回去。