Областная олимпиада по информатике, 2018 год, 10-11 класс
(Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством N объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За d километров придется платить d2 тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить N промо-кодов для поездки на такси со стоимостью X, тогда ему придется платить за каждую поездку X тенге если X≥d, иначе X+(d−X)2 тенге.
Елибай для осмотра объекта под номером i заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно di). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число X, конечно же X должно быть неотрицательным целым числом.
Во второй строке записаны N целых чисел d1,d2,…dn расстояние от офиса до i-го объекта и обратно.
Если X = 6, мы можем получить минимальную стоимость 70.
Суммарно 6×10+(9−6)2+(7−6)2=60+9+1=70
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Ограничения которые присутствуют в тестах:
посмотреть в олимпиаде
Елибай для осмотра объекта под номером i заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно di). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число X, конечно же X должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число N — количество объектов с которыми занимается бизнесмен.Во второй строке записаны N целых чисел d1,d2,…dn расстояние от офиса до i-го объекта и обратно.
Формат выходных данных:
Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число X оптимально.Примеры:
1.Вход:5 7 7 7 7 7Ответ:
352.Вход:
10 2 1 3 6 7 5 9 2 2 4Ответ:
703.Вход:
2 0 100Ответ:
199
Замечание:
Второй пример:Если X = 6, мы можем получить минимальную стоимость 70.
Суммарно 6×10+(9−6)2+(7−6)2=60+9+1=70
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 4 теста: 1≤N≤2000, 0≤di≤1000. В добавок, расстояние до всех объектов одинаково. (di=d1 для i>1)
- 11 тестов: 1≤N≤2000, 0≤di≤1000
- 11 тестов: 1≤N≤2000, 0≤di≤106.
- 24 тестов: 1≤N≤200000, 0≤di≤106.
Комментарий/решение:
Можете подсказать в чем у меня ошибка?
Валится на 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;
}
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.