# Zerojudge c875 : 107北二 2.裝置藝術
## 題目敘述

https://zerojudge.tw/ShowProblem?problemid=c875

給定一排$n$堆的罐子，每個罐子高度為$x$，每堆高度為$a_i$，要求找出移除罐子的最小數且要每個相鄰的堆高度差不超過$y$
$n,a_i,x,y<=10^6$
## 想法 : greedy+set ~~因為我不會用prioirty_queue orz~~

既然只能移除，那我們就由低到高逐一尋訪每一堆。
用一個set<pair<int,int> >去儲存每個堆的資訊，因為要從最低的開始，所以pair的第一個元素設定為堆的高度就可以讓他自動幫我們排列，尋訪每個堆時去看那個堆左右相鄰的堆有沒有比它本身高y以上的，有的話就把ans加上需要移除的罐子數並且同時維護這個set

## 程式碼:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,y;cin>>n>>x>>y;
    int gap=y/x; //直接把單位簡化為罐子的數目，這樣比較好實作
    vector<int>a(n);
    set<pair<int,int> >the;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]); //用cin會超時
        a[i]/=x;
        the.insert(make_pair(a[i],i));
    }
    long long ans=0;
    for(auto i=the.begin();i!=the.end();i++)
    {
        int f=i->first;
        int s=i->second;
        if(s!=0) //查詢目前該堆的左邊，如果這個堆已經在最左邊就不做查詢
        {
            auto p=the.find(make_pair(a[s-1],s-1));//找出該堆左邊鄰居在set裡面的位址
            pair<int,int>cop=*p;
            if(cop.first-f>gap) //如果左邊的堆超過本身gap個罐子以上，就必須移除罐子
            {
                ans+=cop.first-(f+gap);
                the.erase(p); //移除左邊堆舊的資訊
                cop.first=(f+gap);
                a[s-1]=cop.first; //更新左邊堆的原始資訊
                the.insert(cop); //更新左邊堆在set裡的資訊
            }
        }
        if(s!=n-1) //跟查詢左邊的作法一樣
        {
            auto ne=the.find(make_pair(a[s+1],s+1));
            pair<int,int>cop=*ne;
            if(cop.first-f>gap)
            {
                ans+=cop.first-(f+gap);
                the.erase(ne);
                cop.first=(f+gap);
                a[s+1]=cop.first;
                the.insert(cop);
            }
        }
    }
    cout<<ans;
}