题目
在一维坐标轴上,有(n)个点和(m)线段。每次可以花费1移动任意点向左或向右移动一个单位距离。问让每个线段均被至少一个点访问的最小代价。只要有点和线段有交集,该线段就被访问过。
题解
有两个比较简单的处理:
- 如果某些点在线段内,该线段就可以被删除。
- 如果线段内含了更小的线段,那么较大的线段可以被删除。
这个处理可以用数组数组解决。讲线段按照左区间递减排序,右区间递增排序。如果(L, R)包含(l, r),那么有(Lle l le r le R)。那么(l, r)必然排在(L,R)之前。
以下线段用区间代替。这样剩余的区间就和点没有交集,区间之间也不会互相包含。剩余的区间最优方案就是只被1个点访问,并且是距离这个区间最近的两个点中的一个。在两个相邻点之间夹着的区间,最优方案一定是前若干个区间被前一个点访问,剩下的区间被后一个点访问。(感性理解一下)
故最优方案中,每个点访问的区间都是它周围连续的若干个区间。假设点访问左右侧区间的所需的最远距离分别为(a,b),那么最少代价为(2min(a,b)+max(a,b))。这样处理后,就可以用dp解决了。
设(dp[i][j])代表第个(i)点前面的区间都访问好了,并且第(i)点之后的连续(j)个区间会被(i)访问的最小代价。转移方程为
[dp[i][j]=min_{0le k le x}(dp[i-1][k]+2min(a_{k+1,i},b_{i,j}) + max(a_{k+1,i},b_{i,j}))
]
其中:
- (x)代表点(i-1)到点(i)之间的区间数
- (a_{k+1,i})代表点(i)到它右侧的,点(i-1)之后的第(k+1)个的区间的距离。
- (b_{i,j})代表点(i)到它左侧的,点(i)之后的第(j)个的区间的距离。
这个dp是(O(n+m^2))的,需要优化。
(a_{k+1,i})随着(k)增加而减少,(b_{i,j})随着(j)的增加而增加,均是单调的。故可以从小到大枚举(j),从大到小枚举(k),找到临界位置(k'),使得(a_{k'+1} > b_{i,j}),这样就可以把(max)和(min)去掉了,维护一个前缀最小值和后缀最小值即可(O(1))计算出当前的dp值。使用双指针找出临界位置。
最终时间复杂度O(n+m)
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 1e6 + 10;
const double eps = 1e-5;
typedef pair<ll, ll> PII;
vector<int> num;
vector<PII> ret;
int pos[N];
PII segs[N];
ll arr[N];
int tarr[N];
bool del[N];
int mx;
int lowbit(int x) {
return x&-x;
}
void add(int p, int val) {
while(p < mx) {
tarr[p] += val;
p += lowbit(p);
}
}
int get(int p) {
int res = 0;
while(p) {
res += tarr[p];
p -= lowbit(p);
}
return res;
}
int sum(int l, int r) {
return get(r) - get(l - 1);
}
bool cmp(int a, int b) {
if(segs[a].first == segs[b].first) {
return segs[a].second < segs[b].second;
}
return segs[a].first > segs[b].first;
}
int id(int x) {
return lower_bound(num.begin(), num.end(), x) - num.begin() + 1;
}
ll dp[N], tmpdp[N], pre[N], las[N];
int main() {
IOS;
int t;
cin >> t;
while(t--) {
ret.clear();
num.clear();
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
num.push_back(arr[i]);
}
for(int i = 1; i <= m; i++) {
dp[i] = pre[i] = las[i] = 0;
del[i] = 0;
pos[i] = i;
int l, r;
cin >> l >> r;
num.push_back(l);
num.push_back(r);
segs[i] = {l, r};
}
sort(pos + 1, pos + 1 + m, cmp);
sort(num.begin(), num.end());
num.erase(unique(num.begin(), num.end()), num.end());
mx = num.size() + 1;
for(int i = 0; i <= mx; i++) tarr[i] = 0;
for(int i = 1; i <= n; i++) {
add(id(arr[i]), 1);
}
for(int i = 1; i <= m; i++) {
int p = pos[i];
int l = id(segs[p].first), r = id(segs[p].second);
if(sum(l, r)) del[p] = 1;
else add(r, 1);
}
for(int i = 1; i <= m; i++) {
int p = pos[i];
if(del[p]) continue;
ret.push_back(segs[p]);
}
sort(arr + 1, arr + 1 + n);
sort(ret.begin(), ret.end());
int p1 = 0, p2 = 0, prelen, len;
for(int i = 1; i <= n; i++) {
while(p1 < ret.size() && ret[p1].first <= arr[i]) p1++;
while(p2 < ret.size() && (i == n || ret[p2].second <= arr[i + 1])) p2++;
len = p2 - p1;
int sp = prelen;
for(int j = 0; j <= len; j++) {
ll d = j ? ret[p1 + j - 1].first - arr[i] : 0;
if(i == 1) {
ll a = p1 > 0 ? arr[i] - ret[0].second : 0;
tmpdp[j] = 2 * min(a, d) + max(a, d);
} else {
while(sp >= 0) {
ll a = sp < prelen ? arr[i] - ret[p1 - prelen + sp].second : 0;
if(a > d) break;
sp--;
}
tmpdp[j] = las[sp + 1] + d;
if(sp >= 0) tmpdp[j] = min(tmpdp[j], pre[sp] + 2 * d);
}
}
for(int j = 0; j <= len; j++) dp[j] = tmpdp[j];
if(i < n) {
for(int j = 0; j <= len; j++) {
ll d = j < len ? arr[i + 1] - ret[p1 + j].second : 0;
pre[j] = dp[j] + d;
las[j] = dp[j] + 2 * d;
}
for(int j = 1; j <= len; j++) pre[j] = min(pre[j], pre[j - 1]);
for(int j = len - 1; j >= 0; j--) las[j] = min(las[j], las[j + 1]);
}
prelen = len;
}
cout << dp[len] << endl;
}
}