10-11 класс

(Такси) Елібай есімді кәсіпкер Алматы қаласында құрылыс компаниясын басқарады. Қазір оның компаниясы $N$ құрылыс объектісінде жұмыс атқарып жатыр. Оның күнделікті жұмысы — бас кеңседен шығып өз көлігімен құрылыс объектілерін аралап шығу. Қағаз жұмыстарына байланысты, ол бір құрылыс объектісіне барған соң, бас кеңсеге қайтадан оралуы кажет. Бүгін оның жолы болмай, көлігі істен шығып қалды. Кешігіп қалмас үшін, Елібай ZhureBER және Zhett деген такси сервистерінің көмегіне жүгінді. Тариф құны арзан болмай шықты: жүрген $d$ шақырым үшін ол $d^2$ теңге төлеу керек. Оның досы Айсұлтан — жоғарыда айтылған такси сервистерін басқарады. Айсұлтан досына $N$ промо-код сатып алуды ұсынды. Промо-кодтың бағасы $X$ теңгені құрайды. Промо-код қолданарда егер $X \ge d$ болса, Елібай $X$ теңге төлейді, ал егер $X < d$ болса, $X + (d - X)^2$ теңге төлейді.
Елібай $i$ деген нөмірдегі объектіні қарап келу үшін такси шақырады (бас кеңседен объектіге дейінгі жолдың және кері жолдың ұзындығы бірге $d_i$ шақырымды құрайды). Ол бір рет такси шақырған кезде промо-кодты екі рет қолдана алмайды және келесі объектіге бару үшін қайтадан такси шақырады.
Айсұлтан Елібайдың досы болғандықтан, ол Елібайға $X$ санын таңдауға мүмкіндік берді. Әрине, $X$ теріс емес бүтін сан болуы керек. Сіздің тапсырмаңыз — Елібай ақшасын мейлінше аз жарататындай $X$ санын таңдауға көмектесу.

Кіріс деректер форматы:

Бірінші қатарда бір $N$ саны берілген.
Екінші қатарда бос орын арқылы $d_1, d_2, \ldots d_n$ бүтін сандары берілген — олар бас кеңседен кезекті объектіге дейінгі барып қайтқандағы жолдың ара қашықтығын көрсетеді.

Шығыс деректер форматы:

Бір сан шығарыңыз — егер Елібай $X$ санын оптималды таңдаған болса, ол кем дегенде қанша ақша жаратуы қажет.

Мысалдар:

1.Мысал:

5
7 7 7 7 7

Жауап:

35

2.Мысал:

10
2 1 3 6 7 5 9 2 2 4

Жауап:

70

3.Мысал:

2
0 100

Жауап:

199

Түсініктеме:

Екінші мысал:
Егер X = 6 болса, біз кем дегенде 70 теңге жұмсайтын едік.
Барлығына $ 6 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70 $
Егер X = 5 болса, барлық сомма 71 болатын еді. Егерде, X = 7 болып таңдалынса, толық сомма 74 болар еді.

Бағалау:

Есеп 50 тесттен тұрады, әр тест 2 ұпаіға бағаланады.
Тесттердегі шектеулер:

• 4 тестте: $ 1 \le N \le 2000 $, $ 0 \le d_i \le 1000$. Және де объектілерге дейінгі ара қашықтықтар бір-біріне тең ($d_i = d_1 $, егер $ i > 1$).
  
• 11 тестте: $1 \le N \le 2000 $, $ 0 \le d_i \le 1000$
  
• 11 тестте: $1 \le N \le 2000 $, $ 0 \le d_i \le 10^6$.
  
• 24 тестте: $1 \le N \le 200000 $, $ 0 \le d_i \le 10^6$.
  

( Zharaskhan Aman )

Комментарий/решение

@https://paste.ofcode.org/NFzGr99kP2MaXefdbYuBRf_href

Задача решается тернарным поиском по ответу.

можно решить и без тернарного поиска

Можете подсказать в чем у меня ошибка?

Валится на 17 тесте

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,a[200005],imax;

main() {

cin>>n;

for(int i=1;i<=n;i++){

cin>>a[i];

imax=max(imax,a[i]);

}

int l=0,r=1000000;

while(r-l>2){

int m1=l+(r-l)/3,n1=0;

int m2=r-(r-l)/3,n2=0;

for(int i=1;i<=n;i++){

if(m1>=a[i])n1+=m1;

else n1+=m1+pow(a[i]-m1,2);

if(m2>=a[i])n2+=m2;

else n2+=m2+pow(a[i]-m2,2);

}

//cout<<n1<<' '<<n2<<'r'<<endl;

if(n1>=n2){

l=m1;

}

else{

r=m2;

}

}

int ans=0,imin=1e9+7;

for(int j=l;j<=r;j++){

ans=0;

for(int i=1;i<=n;i++){

if(j>=a[i])ans+=j;

else ans+=j+pow(a[i]-j,2);

}

//cout<<j<<' '<<ans<<endl;

imin=min(imin,ans);

}

cout<<imin;

return 0;

}

не знаю, но возможно/ вместо встроенной функции pow(a, b) / просто напиши (a * a);