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

 OI / 洛谷
被浏览 次

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

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

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

我们应选择复杂度为 (NlogN)(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);
}
 上一页