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

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

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

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

 

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

 

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

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

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

هر بازیکن در هر حرکت می‌تواند یک بازه از ستون‌ها را انتخاب کند و به هرکدام یک مربع اضافه کند. (در واقع بازیکن اعداد l و  را انتخاب میکند و سپس به ازای هر  ، مقدار  را یکی زیاد می‌کند.)

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

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

 

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

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

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

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

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

 

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

#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;
}

 

 

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

 

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

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

موفق باشید.

 

 

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

برای امتیاز به این نوشته کلیک کنید!
[کل: 0 میانگین: 0]