پاسخ سوال تتریس + کوئرا

پاسخ سوال تتریس + کوئرا

در این نوشته تمرین “تتریس” که در وب‌سایت کوئرا موجود می‌باشد را برای شما کاربران عزیز حل کرده‌ایم.

در مورد سایت کوئرا بیش‌تر بخوانید…

تمرین تتریس کوئرا + سی پلاس پلاس

توی دوره نیمبو به تفریح کارآموزها اهمیت زیادی داده می‌شه و واسه همین تو زمان استراحت به کارآموزا می‌گن که بازی تتریس نیمبویی رو بازی کنن تا هم یه تفریحی واسشون باشه هم زمان استراحت یه جوری بگذره.

در بازی تتریس نیمبویی n ستون وجود دارند که از چپ به راست با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند و ستون i ام از ai​ مربع واحد تشکیل شده‌است.

هر بازیکن در هر حرکت می‌تواند یک بازه از ستون‌ها را انتخاب کند و به هرکدام یک مربع اضافه کند. (در واقع بازیکن اعداد l و $r$ را انتخاب میکند و سپس به ازای هر $l\le j\le r$ ، مقدار aj​ را یکی زیاد می‌کند.)

هدف بازی یکسان کردن طول تمام ستون ها در کم‌ترین تعداد مرحله است.

حالا مهرداد که از این بازی خوشش نیومده ازتون می‌خواد تا بهش بگین که این کم‌ترین تعداد مرحله چندتاست تا بتونه سریع بازی رو تموم کنه و به بقیه کاراش برسه.

ورودی سوال تتریس

در خط اول ورودی عدد $n$ ، تعداد ستون‌ها می‌آید.

در خط بعدی $n$ عدد آمده که عدد $i$ ام آن a_{i}ai​ است که تعداد مربع‌های ستون $i$ ام را نشان می‌دهد.

$$1\le n\le 1000000$$

1 ≤ ai​ ≤ 1000000000

خروجی سوال تتریس

در خروجی یک عدد که کم‌ترین تعداد مراحل برای رسیدن به هدف بازی است را چاپ کنید.

حل سوال تتریس (به زبان برنامه نویسی سی پلاس پلاس)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k;
ll a[1000001];
ll ans = 0;
int mid_max(int l, int r)
{
    int maxi=-1, max_id;
    int mid = (l+r)/2;
    for(int i=l; i<=r; i++)
    {
        if(a[i] > maxi)
            maxi = a[i], max_id=i;
        else if(a[i] == maxi && abs(mid-i) < abs(mid-max_id))
            max_id = i;
    }
    return max_id;
}
 
void solve(int l, int r, int e)
{
    if(l > r) return;
    if(l == r)
    {
        ans += k-(a[l]+e);
        return;
    }
    int midmax = mid_max(l, r);
    
    ans += k - (a[midmax]+e);
    e += k - (a[midmax]+e);
    solve(l, midmax-1, e);
    solve(midmax+1, r, e);
}
 
int main()
{
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    ll* max_id = max_element(a, a+n);
    k = *max_id;
    solve(0, n-1, 0);
    cout << ans << endl;
    return 0;
}

منبع سوال: وبسایت کوئرا

اگر روش حل بهتری برای “تمرین تتریس” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم.

اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.

موفق باشید.

پیشنهاد نویسنده: سورس بازی تتریس