D. Trash Problem
题意
给出n<1e5个不重复的点表示n个物品在x轴上的位置1<=pos<=1e9
要求将物品整理成最多2堆,
每次可以将一堆物品(在pos1)移动到某个位置(pos2) 消耗abs(pos2-pos1)的体力
当某些物品在同一个位置时就成为一堆 将被一起移动 移动消耗的体力仍然按距离算
q(1e5)组询问
每次输入两个数ops和pos
当ops=0时表示在上一次询问状态下 删除掉pos位置上的物品
当ops=1时表示在上一次询问状态下 在pos位置上增加物品
每次询问输出能将物品全部整理好的最少消耗体力
题解
当我们将所有物品汇聚到一堆时消耗的最少体力显然=最右端物品位置-最左端物品位置
显然当物品大于2个的时候分成两堆更省力
最少消耗体力=最右端物品位置-最左端物品位置-最大相邻物品的间隔
(自己想当然的觉得以最右端和最左端的中间点为分割点 左半边归一堆，右半边归一堆)
剩下问题是如何处理多组询问
set具有优秀的查询能力 所以我们选择维护一个储存位置信息的set 和一个间距信息的multiset
每次询问时 ：
若加入一个新物品 x 则 需要在set中加入x的位置
同时在multiset里删除 x下一个物品的位置-x上一个物品的位置；
在multiset里加入x下一个物品的位置 - x的位置
在multiset里加入x的位置 - x上一个物品的位置
若删除一个物品 x 则 需要在set删除x的位置
同时在multiset里加入 x下一个物品的位置-x上一个物品的位置；
在multiset里删除x下一个物品的位置 - x的位置
在multiset里删除x的位置 - x上一个物品的位置
- 注意上述操作需要判断插入/删除是否发生在最右端或最左端
这里需要特别提醒set的一些用法误区和一些小技巧
set的end()返回的是set的size并不是最后一个元素
set的erase()参数可以是值也可以是值对应的指针
multiset中erase()删除某个值(key)代表删除所有等于这个值的元素,
若只想删除其中一个则使用multset.erase(multset.find(key) )
set的find(key)时间复杂度为logn 返回key的指针
插入单个元素会返回一个 pair<iterator，bool> 对象
注意set的指针对应元素会在插入/删除操作后产生变化
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const ll Mod=998857459;
set<int>piles;
multiset<int>gap;
vector<int>arr;
int main() {
Turnoff;
int n,q;cin>>n>>q;
int last=0;
for(int i=1;i<=n;i++){
int temp;cin>>temp;
arr.push_back(temp);
piles.insert(temp);
}
sort(arr.begin(),arr.end());
for(int i=1;i<arr.size();i++)gap.insert(arr[i]-arr[i-1]);
if(piles.size()<=2)cout<<0<<endl;
else{
int maxpos=*(--piles.end()),minpos=*(piles.begin());
int maxgap=*(--gap.end());
cout<<maxpos-minpos-maxgap<<endl;
}
while(q--){
int op,pos;cin>>op>>pos;
if(op){
auto it=piles.insert(pos).first;
if(next(it)!=piles.end())gap.insert(*next(it)-pos);
if(it!=piles.begin())gap.insert(pos-*prev(it));
if(it!=piles.begin()&&next(it)!=piles.end())gap.erase(gap.find(*next(it)-*prev(it)));
}
else {
auto it=piles.find(pos);
if(next(it)!=piles.end())gap.erase(gap.find(*next(it)-pos));
if(it!=piles.begin())gap.erase(gap.find(pos-*prev(it)));
if(it!=piles.begin()&&next(it)!=piles.end())gap.insert(*next(it)-*prev(it));
piles.erase(pos);
}
if(piles.size()<=2)cout<<0<<endl;
else{
int maxpos=*(--piles.end()),minpos=*(piles.begin());
int maxgap=*(--gap.end());
cout<<maxpos-minpos-maxgap<<endl;
}
}
}
|