CJOJ 1308 【HNOI 2002 】营业额统计 / CodeVS 1296 营业额统计（STL，二分）

Description

Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}。

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。

第一天的最小波动值为第一天的营业额。

Input

第一行为正整数n(n＜=32767)，表示该公司从成立一直到现在的天数，接下来的n行每行有一个正整数ai(ai＜=1000000)，表示第i天公司的营业额。

Output

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。

Sample Input

6

5

1

2

5

4

6

Sample Output

12

Http

CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1308

CodeVS:http://codevs.cn/problem/1296/

Source

STL

题目大意

在一列数中，设F[i]表示第i个数与前i-1个数的差的绝对值的最小值，现在求 F[1] + F[2] + …… F[n]，F[1]就为第i个数

解决思路

虽然说这是一道省选难度的题目，但如果用STL+二分查找来解决，还是比较好实现的。

首先我们用一个set来依次存放营业额。为了方便叙述，我们假定当前输入的第i天的营业额为value，先不把value放入set。首先判断set中是否有value了，若已经有了value，说明以前有一天有一模一样营业额，那么这一天的最小波动值就为0。否则二分查找出刚好比value大和刚好比value小的两个数，比较差值即可。

在二分查找的时候，我们使用的是STL自带的lower_bound函数。lower_bound(value)返回的是一个刚好大于等于value的迭代器（具体情况可以自行百度）。所以lower_bound返回后我们要让其-1使得满足刚好比value小（set里面没有重复 ），至于求刚好比value大的就可以直接是lower_bound的返回值。查找完后，再把value放入set中。

另外需要注意的是，set如果为空那么用lower_bound查找会RE，所以应该先读入一个数并放入set中。正好这道题的第一天确实需要特殊处理一下（因为第一天的最小波动值就是营业额），所以在循环外读入并处理。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<set>

#include<algorithm>

using namespace std;

const int maxN=40000;

const int inf=2147483647;

int n;

set<int> Set;

int main()

{

    int value;

    int Ans;

    cin>>n;

    cin>>Ans;//一定要先读入一个，否则会出错

    Set.insert(Ans);

    for (int i=2;i<=n;i++)

    {

        if (scanf("%d",&value)==EOF)

        {

            value=0;

        }

        if (Set.count(value)==0)//如果为1则说明已经有过一样的营业额了，所以最小值为0

        {

            int a=*(--Set.lower_bound(value));//比value刚好小的数

            int b=*(Set.lower_bound(value));//比value刚好大的数

            if (Set.count(a)==0)//有可能出现找不到或返回空的情况

                Ans+=abs(b-value);

            else if (Set.count(b)==0)

                Ans+=abs(a-value);

            else

                Ans+=min(abs(a-value),abs(b-value));

        }

        Set.insert(value);

    }

    cout<<Ans<<endl;

    return 0;

}