[题解] LP2234 [HNOI2002] 营业额统计

ajcxsu
ajcxsu 2018年02月25日
  • 20 次阅读

Problem

自行原题面。

Solution

multiset在insert时支持返回迭代器
则每次摸着迭代器找就行了。

为了简化问题,插入inf和-inf来避免RE。

Code

// Code by ajcxsu
// Problem: LP2234

#include<bits/stdc++.h>
using namespace std;

multiset<int> x;

int tmin(int a,int b,int c) {
    a=(a<b?a:b);
    a=(a<c?a:c);
    return a;
}

int main() {
    x.insert(0x3f3f3f3f),x.insert(-0x3f3f3f3f);
    int n;
    cin>>n;
    long long tot=0;
    int na,ans;
    multiset<int>::iterator it;
    cin>>na;
    x.insert(na);
    tot+=na;
    while(n--) {
        cin>>na;
        it=x.insert(na);
        auto itb=it,itc=it;
        itb--;
        itc++;
        if(*itb==-0x3f3f3f3f) tot+=abs(*itc-*it);
        else if(*itc==0x3f3f3f3f) tot+=abs(*it-*itb);
        else tot+=min(abs(*itc-*it), abs(*it-*itb));

    }
    cout<<tot<<endl;
    return 0;
}

本文链接:https://acxblog.site/archives/sol_luogu_2234.html
本文采用 CC BY-NC-SA 3.0 协议进行许可