Областная олимпиада по информатике, 2018 год, 10-11 класс

(Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством $N$ объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За $d$ километров придется платить $d^2$ тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить $N$ промо-кодов для поездки на такси со стоимостью $X$, тогда ему придется платить за каждую поездку $X$ тенге если $X \ge d$, иначе $X + (d - X)^2$ тенге.
Елибай для осмотра объекта под номером $i$ заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно $d_i$). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число $X$, конечно же $X$ должно быть неотрицательным целым числом.

Формат входных данных:

Первая строка входного файла будет содержать одно число $N$ — количество объектов с которыми занимается бизнесмен.
Во второй строке записаны $N$ целых чисел $d_1, d_2, \ldots d_n$ расстояние от офиса до $i$-го объекта и обратно.

Формат выходных данных:

Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число $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);