یکی از سخت ترین سوالات برنامه نویسی

Question

آب

شهر مقدّس آنیتا در یونان باستان شهری بود که تمام ساختمان­‌های آن در یک ردیف ساخته شده بود. با وجود قدیمی بودن، این شهر از ساختمان­‌های بلند ساخته شده بود و همچنین عرض هر ساختمان در این شهر دقیقا ۱ متر بود. نقل است که در این شهر، به هنگام بارش باران آب تا جای ممکن بر روی ساختمان­‌ها جمع می­‌شود. در واقع اگر این شهر را روی یک خط از راست به چپ در نظر بگیریم، آب جمع شده روی ساختمان­ها فقط از راست و چپ می­‌ریخت.

در یونان قدیم، یک سال کامل باران آمد. می‌خواهیم ببینیم در این صورت روی سقف ساختمان‌­های آنیتا حداکثر چه مقدار آب جمع شده است.

ورودی

در سطر اوّل ورودی عدد طبیعی $n$ (تعداد ساختمان‌ها) آمده است.

در سطر بعد $n$ عدد آمده است که به ترتیب ارتفاع ساختمان‌ها را از راست به چپ مشخّص می‌کنند و با فاصله از هم جدا شده اند.

ارتفاع هر ساختمان حداکثر ۱۰۰۰ متر خواهد بود.$$1\le n\le 1000000$$

خروجی

در تنها خط خروجی حداکثر میزان آب جمع شده روی سقف ساختمان‌های شهر آنیتا (بر حسب متر مربّع) بنویسید.

 

 

 

 

 

Answer 1

#include<iostream>

using namespace std;
const int maxn = 1000000;

int n,m[maxn],ans,a[maxn],j[maxn],z,save;

int main()
{

    cin>>n;
    for (int i=0;i<n;i++)
        cin>>a[i];
    m[n-1]=a[n-1];
    j[n-1]=n-1;
    for (int i=n-2;i>=0;i--)
    {
        m[i]=m[i+1];
        j[i]=j[i+1];
        if (a[i]>m[i+1])
        {
            m[i]=a[i];
            j[i]=i;
        }
    }
    while (z!=n-1)
    {
        if (m[z+1]<a[z])
        {
            for (int i=z+1;i<j[z+1];i++)
                ans+=(m[z+1]-a[i]);
            z=j[z+1];
        }
        else
        {
            for (int i=z+1;i<n;i++)
            {
                if (a[i]>=a[z])
                {
                    save=i;
                    break;
                }
            }
            for (int i=z+1;i<save;i++)
                ans+=(a[z]-a[i]);
            z=save;
        }
    }
    cout<<ans;
    
    return 0;
}