洛谷P 234[HNOI 2002]売上高統計(set)+set基礎知識

洛谷P 234[HNOI 2002]売上高統計(set)+set基礎知識テーマ転送ゲート
タイトルの説明
Tigerは最近、会社から営業部のマネージャーに昇進し、就任後、会社から与えられた最初の任務は、会社の設立以来の営業状況を統計し、分析することだ.
Tigerは会社の帳簿を取り出し、帳簿には会社設立以来の毎日の売上高を記録した.営業状況を分析するのはかなり複雑な仕事です.休日、大安売りやその他の場合、売上高に一定の変動が生じるため、当然一定の変動は受け入れられるが、時には売上高が高くなったり低くなったりして、会社の経営状況に問題があることを証明している.経済管理学では、この状況を測定するために最小変動値を定義しています.
最小変動値が大きいほど、営業状況が不安定であることを示します.
会社全体の設立から現在までの営業状況が安定しているかどうかを分析するには、毎日の最小変動値を加算するだけでいい.あなたの任務はプログラムを作成してTigerを助けてこの値を計算することです.
初日の最小変動値は初日の売上高です.
その日の最小変動値=min{|その日以前の日の売上高-その日の売上高|}です.
入力フォーマット
1行目の正の整数n(n<=32767)は、同社が設立から現在までの日数を表し、次のn行の各行に1つの整数ai(|ai|<=100000)があり、i日目の会社の売上高がマイナスになる可能性があることを示している.
入出力サンプル入力#16 5 1 2 5 4 6
出力#112
今年の2月に優先行列を知って便利でした!離陸~~~この分析問題の意味は少し優先列の味がします.しかし、重要な操作は、現在の値以上の最初の値を取得することです.ではsetの方が便利です.
lower_bound(key_value)は、key_以上の最初の値を返します.valueのロケータupper_bound(key_value)は、keyより大きい最後の値を返します.valueのロケータ

#include 
#include 
 
using namespace std;
 
int main()
{
	set<int> s;
	for(int i = 1;i <= 5;i ++)
	{
		int x;
		cin >> x;
		s.insert(x);
	}
	set<int>::iterator iter;
	for(iter = s.begin() ; iter != s.end() ; ++iter)
	{
		cout << *iter << " ";
	}
	cout << endl;
	cout << "        2    :   ";
		cout<<*s.lower_bound(2)<<endl;
	cout << "        3    :   ";
		cout<<*s.lower_bound(3)<<endl;
	cout << "      3    :   ";
		cout<<*s.upper_bound(3)<<endl;
	return 0;
}

基本的な使い方は以下の通りです.

set<int> my_set;
my_set.insert(a);
my_set.erase(iter); //     
my_set.clear();
my_set.empty();
my_set.begin();
my_set.end();
my_set.size();
my_set.find(a);   //     

my_set.rbegin();		  // my_set.rbegin() = my_set.end()-1;
my_set.rend();           // my_set.rend() = my_set.begin()+1;

my_set.lower_bound(key_value)   //         key_value    
my_set.upper_bound(key_value)  //        key_value    

問題解決コード:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long

set<int> s;
set<int>::iterator p,pr;
int main(){
    int ans=0,n,i,x;
    cin>>n;
    s.insert(10000005);
    s.insert(-100000005);
    for(i=0;i<n;i++){
        cin>>x;
        if(s.size()==2)
            ans+=x;
        else {
            p=s.lower_bound(x);
            pr=p;
            pr--;
            ans+=min(abs(*pr-x),abs(*p-x));
        }
        s.insert(x);
    }
    cout<<ans;
}

この問題の最大値と最小値にはこだわりがある.何のごみのデータは何度試みてやっとAC吐きましたうん!いい問題だ!