洛谷P2234 - 「HNOI2002」营业额统计

 题解 / 洛谷
被浏览

根据题意我们发现对于每个$A_{i}$,与它绝对值最小的一定是前$i$个数排序后在它前面或后面的数。

这样的话,我们维护一个单调的序列,插入每天的营业额时计算其波动值即可。

最暴力的便是插入排序,复杂度$(N^2)$,不能忍受。。

我们应选择复杂度为$(NlogN)$的方法。

维护一个单调序列自然想到了 set(平衡树也可以,但是作者懒,想用 STL 水过去,逃……),因为可能有多个相同的营业额,所以我选择了 multiset。

下次有空写一个 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
#include<cstdio>
#include<set>
using namespace std;
typedef multiset<int>::iterator iter;
// 定义iter类型,免去每次打一大串的苦恼
const int inf=0x7fffffff;
int n,x,ans;
multiset<int>s;
inline int min(int a,int b){return a<b?a:b;}
inline int abs(int x){return x<0?-x:x;}
int main(){
s.insert(inf);s.insert(-inf);
// 插入正无穷和负无穷,防止迭代器访问到一些奇奇怪怪的内存导致RE
scanf("%d",&n);
scanf("%d",&x);s.insert(x);ans=x;
// 第一个单独考虑
while(--n){
scanf("%d",&x);
iter it=s.insert(x);
// 插入x,并返回x在s中的位置(迭代器)
it--;
iter l=it;
it++;it++;
iter r=it;
it--;
// 迭代器只支持++,--运算符,所以看上去很麻烦。。
// 其实l就是上一个数,r是下一个数(在s中)
if(*l==-inf)ans+=abs(x-*r); // 在最前面
if(*r==inf)ans+=abs(x-*l); // 在最后面
if(*l!=-inf&&*r!=inf)ans+=min(abs(x-*r),abs(x-*l));// 一般情况
}
printf("%d",ans);
}
 上一页