Тема: Algotester, задача #40427 "Новий рік"
Використання бінарного пошуку для вирішування задачі
Зараз застрягла на цій задачці:
https://algotester.com/uk/ArchiveProble … itor/40427
Або:
Діти на засніженому подвір’ї зробили, себто накатуляли, багато снігових куль. І от настав час іти додому. Але ж дітям не хочеться залишати їхні неймовірні снігові шедеври надворі. От і вирішили вони позабирати їх до хати. Мама кожної дитини дозволяє їй занести до хати не більше ніж одну кулю, або її частинку. Ба більше, якщо якесь дитинча візьме додому більшу частину, то інше на нього образиться.
От діти і задумались над тим, яким чином занести до їхніх домівок максимальну кількість снігу. Причому всі несуть додому по одному куску кулі однакового об’єму. Діти можуть ділити кулі, які вони мають в наявності як завгодно, але ліпити два куски докупи вони не можуть (сніг дуже сухий попався).
Вам необхідно знайти максимально можливий сумарний об’єм снігу, який діти зможуть рознести по своїх домівках.
Вхідні дані
У першому рядку містяться два цілих числа n і m — кількість дітей та кількість снігових куль.
Наступні m рядків містять по одному цілому числу r з індексом i — радіусу відповідної кулі.
Вихідні дані
У єдиному рядку виведіть дійсне число — максимальний можливий об’єм снігу. Відповідь уважатиметься правильною, якщо абсолютна або відносна похибка не перевищуватиме 10^(-4).
Обмеження
1≤ n, m ≤10^(5),
1≤ r з індексом і ≤100.
Є проблема з тим випадком, коли снігових куль менше за кількість дітей. В наступному коді я використовую бінарний пошук для вирішення цієї задачі:
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
const long double pi = M_PI; // 3.1415926535897932384626433832795;
void QuickSort(int radius[], int first, int last);
double maximum(long double snow[], int children, int snowballs);
using namespace std;
int main() {
int children = 1, snow_balls = 1;
cin >> children >> snow_balls;
int *snow_radius = new int[snow_balls];
for(int i = 0; i < snow_balls; i++) {
cin >> snow_radius[i];
}
QuickSort(snow_radius, 0, snow_balls - 1);
long double *new_snow = new long double[snow_balls];
for(int i = 0; i < snow_balls; i++) {
new_snow[i] = (snow_radius[i] * snow_radius[i] * snow_radius[i] * pi * 4) / 3;
}
cout << fixed << setprecision(10) << maximum(new_snow, children, snow_balls) * children;
delete[] new_snow;
delete[] snow_radius;
return 0;
}
void QuickSort(int snow_radius[], int first, int last) {
int middle = (first + last) / 2;
int left_bound = first;
int right_bound = last;
do {
while(snow_radius[left_bound] > snow_radius[middle]) {
left_bound++;
}
while(snow_radius[right_bound] < snow_radius[middle]) {
right_bound--;
}
if(left_bound <= right_bound) {
swap(snow_radius[left_bound++], snow_radius[right_bound--]);
}
} while(left_bound <= right_bound);
if(left_bound < last) QuickSort(snow_radius, left_bound, last);
if(right_bound > first) QuickSort(snow_radius, first, right_bound);
}
double maximum(long double snow[], int children, int snow_balls) {
long double left_bound = 0, right_bound = ((pow(100, 3) * pi * 4) / 3) + 1;
int max_value = min(children, snow_balls);
long double mid_radius;
int max_radius;
double eps = 1e-7;
while(right_bound - left_bound > eps) {
mid_radius = (left_bound + right_bound) / 2;
max_radius = 0;
for(int j = 0; j < max_value; j++) {
max_radius += snow[j] / mid_radius;
}
if(max_radius >= children)
left_bound = mid_radius;
else
right_bound = mid_radius;
}
return left_bound;
}Я перевіряла на всі можливі інпути, перевіряла через чат-gpt (не сильно допомогло), але кожного разу виникає "неправильна відповідь" у 16 тесті на сайті з задачею. Можливо у мене проблеми з округленням, хоч я максимально округляю об'єм кулі.
