题意
设第 $i$ 天的营业额为 $a_{i}$, 则第 $i$ 天 $(i \geq 2)$ 的最小波动值 $f_{i}$ 被定义为:
要求计算每一天的最小波动值的和。
第一天的最小波动值为第一天的营业额 $a_{1}$ 。
思路
众所周知，set能有序地维护同一类型的元素，但相同的元素只能出现一次。
对于这道题来说，我们可以用set来记录下之前出现过的所有营业额。
每次输入一个新的数x后，通过lowerbound操作找到set中大于等于x的第一个数。
- 如果这是第一个数，直接插入到set里。
- 这个数等于x,显然最小波动值为0，我们也不需要再插入一个x放到set里了。
- 这个数大于x,通过set的特性可以很轻松的找到这个数的前驱，也就是小于x的第一个数。将两个数分别减去x,对绝对值取个min就好了。此时要将x插入到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
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
const int N = 100010;
int n,x;
set<int> st;
LL ans;
int main()
{
st.insert(-0x3f3f3f3f);
st.insert(0x3f3f3f3f);
scanf("%d",&n);
while(n--){
scanf("%d",&x);
auto tp = st.lower_bound(x);
if(st.size()==2){
ans+=x;
st.insert(x);
}else if(*tp!=x){
int nw=*tp,nx=*(--tp);
ans+=min(abs(x-nw),abs(x-nx));
st.insert(x);
}
}
printf("%lld\n",ans);
return 0;
}
|
总结
set可以在很多问题上代替平衡树，auto t = lower_bound(x)是找第一个大于等于x的数返回迭代器，*t是它的值。++和—操作可以寻找前驱和后继。
- lower_bound(x)是找第一个大于等于x
- upper_bound(x)是找第一个大于x
题意
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入数值 xx。
- 删除数值 xx(若有多个相同的数，应只删除一个)。
- 查询数值 xx 的排名(若有多个相同的数，应输出最小的排名)。
- 查询排名为 xx 的数值。
- 求数值 xx 的前驱(前驱定义为小于 xx 的最大的数)。
- 求数值 xx 的后继(后继定义为大于 xx 的最小的数)。
思路
因为vector支持erase，insert。可以用它来搞平衡树（时间慢一点）。
代码
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
| #include<vector>
#include<cstdio>
#include<algorithm>
int main()
{
int n,op,x;
scanf("%d",&n);
std::vector<int>a;
a.reserve(n);
while(n--)
{
scanf("%d%d",&op,&x);
switch(op)
{
case 1:a.insert(upper_bound(a.begin(),a.end(),x),x); break;
case 2:a.erase(lower_bound(a.begin(),a.end(),x));break;
case 3:printf("%ld\n",lower_bound(a.begin(),a.end(),x)-a.begin()+1);break;
case 4:printf("%d\n",a[x-1]);break;
case 5:printf("%d\n",*(--lower_bound(a.begin(),a.end(),x)));break;
case 6:printf("%d\n",*(upper_bound(a.begin(),a.end(),x)));break;
}
}
return 0;
}
|
总结
