【BZOJ 1588】 [HNOI2002]营业额统计

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

每天的最小波动值指的是和之前所有天的差值的绝对值中的最小值。

用set.的lower_bound函数。

每次找和他差值最小的数字就好。

(不要用lower_bound(myset.begin(),myset.end(),x)

这个比较慢

而应该用myset.lower_bound(x)

就能ac了

【代码】

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <set>

using namespace std;

int n;

long long ans = 0;

set<int> myset;

int main(){

    //freopen("D:\\rush.txt","r",stdin);

    scanf("%d",&n);

    for (int i = 1;i <= n;i++){

        int x;

        scanf("%d",&x);

        if (i==1) ans = x;else{

            int temp = -1;

            set<int>::iterator pos = myset.lower_bound(x);

            int temp1 = (*pos);

            temp1 = abs(temp1-x);

            if (pos!=myset.end()) temp = temp1;

            if (pos!=myset.begin()){

                pos--;

                temp1 = (*pos);

                temp1 = abs(temp1-x);

                if (temp==-1)

                    temp = temp1;

                else

                    temp = min(temp1,temp);

            }

            ans+=temp;

        }

        myset.insert(x);

    }

    printf("%lld\n",ans);

    return 0;

}