Есть некое бинарное дерево поиска. У него есть корень. Левое и правое поддерево тоже являются бинарными деревьями. Вводится число, если оно меньше корня - переходим в левое поддерево, если больше - в правое рекурсивно. И если нашелся NULL, то запишем туда. Если хочешь узнать подробнее - погугли "бинарное дерево поиска"
в каком месте перебор 100000 элементов (максимум по условию задачи) выбивается за 1/10 секунды?)) мне просто интересно, как ты считал.
ну, я банально вбил код считать элементы + перебрать их, и закинул код в компилятор на сайте (C#), и крч половина вариантов просто не прошла по времени ору
я не знаю че ты там за код написал, ТС скинул свой код через multiset, по времени он только в последний тест немного не уложился. если ты написал тупой перебор всех комбинаций с поиском максимума, то конечно это медленно
Нет, просто у него плюсы. На c# на считывание идет больше времени, чем в плюсах. Но они же должны были это учесть при создании задачи, вот о чем я
Если бы... всё так же в 0.1 секунду
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp13
{
class Program
{
static void Main(string[] args)
{
double[] NP = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse);
double p = 1 - ((double)NP[1] / 100.0);
List<double> mass = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse).OrderBy(j => j).ToList();
//Дальше алгоритм прост: ебашим цикл священной инквизиции, удаляя приплюсованные элементы. Саму плюсовщину мы заранее ещё и в процентную преобразуем.
Ну и в самом начале всё выставляем "на вырост". Да, i=-1 нужна хрень, без неё ничо не работает, хз почему, но цикл сразу решает единицу прибавить и крщ мне просто лень с этим разбираться
for(int i = 0; i <NP[0]-1; i++)
{
mass = mass.OrderBy(j => j).ToList();
mass[i] += mass[i + 1];
mass[i] *= p;
mass.RemoveAt(i + 1);
NP[0]--;
i = -1;
}
//а тут "типаправильное" округление
Console.WriteLine("{0:0.00}", Math.Round(mass[0],2));
}
}
}а, да я тупо рекурсию создал так хддд я как раз те рандомные варианты прописывал для самопроверки и крщ забыл удалить отправку метода рандома лл
ну значит у тебя крашится прога
едрить программист от бога)
List<double> mass = new List<double>();
foreach (String s in Console.ReadLine().Split())
{
if (!string.IsNullOrEmpty(s)) {
mass.Add(double.Parse(s));
}
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp13
{
class Program
{
static void Main(string[] args)
{
double[] NP = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse);
double p = 1 - ((double)NP[1] / 100.0);
List<double> mass = new List<double>();
foreach (String s in Console.ReadLine().Split())
{
if (!string.IsNullOrEmpty(s)) {
mass.Add(double.Parse(s));
}
}
while(NP[0] > 1)
{
mass = mass.OrderBy(j => j).ToList();
mass[0] += mass[1];
mass[0] *= p;
mass.RemoveAt(1);
NP[0]--;
}
Console.WriteLine("{0:0.00}", Math.Round(mass[0],2));
}
}
}Смотри пример:
но multiset же сам сортирует. Если такого в C# нет такого - можешь сделать с помощью RB дерева
Ну вот я и слелал сортировку после каждого суммирования
я дико извиняюсь, но хочется уже с приличных слов перейти на неприличные.
multiset всегда отсортирован. не потому что он после каждой вставки сортирует сам себя, а потому что у него такая структура, что вставка элемента происходит быстро и не нарушает сортированность. читай про деревья поиска.
