本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
题目链接：https://codeforces.ml/contest/1418/problem/D
题意：给定n个点 每个点代表有一堆垃圾， 每个点至多只会有一堆垃圾，有两种操作
一种操作是清理掉 i 处的垃圾， 一种是在i处添加一堆垃圾 每次扫垃圾可以把i 的垃圾全部扫去i+1或者i-1
每次询问最少需要多少步 才能把垃圾扫成不大于两堆
思路：先考虑变成一堆的，那么无论怎么移动 答案都是最大的数减去最小的数
那么两堆的考虑分去左右两边各一堆，那么肯定就是从中间开始分界，发现左边的堆和右边的堆肯定不会产生交集
如果产生交集，那么把交集的地方划入另外一堆就会更优 所以最后的答案ans=max-min-temp temp为所有相邻数数的间隔的最大值
只需要一个set维护最大最小值 一个multiset维护间隔即可， 每次处理的要特别注意一下 插入/删除的数在开头或者末尾的情况 用 it 来处理位置
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define ll long long
4 #define pb push_back
5 const int maxn =1e5+10;
6 const int mod=998244353;
7 int a[maxn];
8 multiset<int>g;
9 set<int>s;
10
11 void query()
12 {
13 if(s.size()<=1)
14 {
15 cout<<0<<'\n';
16 return;
17 }
18 int max1=*s.rbegin();
19 int min1=*s.begin();
20 int gap=*g.rbegin();
21 cout<<max1-min1-gap<<'\n';
22 }
23
24
25 int main()
26 {
27 ios::sync_with_stdio(false);
28 cin.tie(0);
29 int n,q;
30 cin>>n>>q;
31
32 for(int i=1;i<=n;i++)
33 {
34 cin>>a[i];
35 s.insert(a[i]);
36 }
37 sort(a+1,a+1+n);
38 for(int i=1;i<n;i++)
39 {
40 g.insert(a[i+1]-a[i]);
41 }
42 query();
43 while(q--)
44 {
45 int c,x;
46 cin>>c>>x;
47 if(c)
48 {
49 s.insert(x);
50 auto it1=s.find(x);;
51 auto it2=it1;
52 auto it3=it2;
53 it3++;
54 if(it2!=s.begin())
55 {
56 it1--;
57 int add=(*it2)-(*it1);
58 g.insert(add);
59 }
60 if(it3!=s.end())
61 {
62 int add=(*it3)-(*it2);
63 g.insert(add);
64 }
65 if(it2!=s.begin()&&it3!=s.end())
66 {
67 int sub=(*it3)-(*it1);
68 g.erase(g.find(sub));
69 }
70 }
71 else
72 {
73 auto it1=s.find(x);;
74 auto it2=it1;
75 auto it3=it2;
76 it3++;
77 if(it2!=s.begin())
78 {
79 it1--;
80 int sub=(*it2)-(*it1);
81 g.erase(g.find(sub));
82 }
83 if(it3!=s.end())
84 {
85 int sub=(*it3)-(*it2);
86 g.erase(g.find(sub));
87 }
88 if(it2!=s.begin()&&it3!=s.end())
89 {
90 int add=(*it3)-(*it1);
91 g.insert(add);
92 }
93 s.erase(x);
94 }
95 query();
96 }
97
98
99
100 }
View Code
