Где ошибка в простом алгоритме?

460
12 мая 2022, 07:00

Написал простой алгоритм для решения данной задачки:

Почему-то не проходит 3 проверки из 25. Проганял много своих тестов, всё хорошо, работает как надо, но почему-то не проходит 3 теста. Как исправить ?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main() {
    int n, b, mx=-1, mx1=-201, SAME=0;
    cin >> n;
    vector<int> vec(101,0);
    vector<double> SAMEnums;
    for (int i = 0; i < n; i++)
    {
        cin >> b;
        vec[b]++;
    }
    for (int i = 1; i < 101; i++)
    {
        if (vec[i] == 0) vec[i] = -2;
    }
    //-----------------------------------------------------------------------
    for (int i = 1; i < 101; i++)
    {
        if (vec[i] > mx)
        {
            mx = vec[i];
            mx1 = i;
            SAMEnums.clear();
            SAMEnums.push_back(i);
        }
        else if (vec[i] == mx)
        {
            SAMEnums.push_back(i);
        }
    }
    //-----------------------------------------------------------------------
    double size = SAMEnums.size();
    if (size==1)  
    {
        cout << mx1;
        return 0;
    } 
    if (size > 1)  
    {
        double sum = 0;
        double average;
        for (int i = 0; i < size; i++)
        {
            sum += SAMEnums[i];
        }
        average = sum / size;
        SAMEnums.push_back(average);
        sort(SAMEnums.begin(), SAMEnums.end());
        int averindex=0;
        for (int i = 0; i < size; i++)
        {
            if (SAMEnums[i] == average) averindex = i;
        }
        if (average - SAMEnums[averindex-1] <= abs(average - SAMEnums[averindex + 1])) cout << SAMEnums[averindex-1];
        else cout << SAMEnums[averindex+1];
    }
}

Так же проверял типы данных, может числа проверок большие, но нет, ставил long int и long double, это никак не влияет

Answer 1

Откровенно говоря, мне всегда тяжелее копаться в чужом коде, чем написать свой...

#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
    struct data { int h, c; }; // Высота и количество
    int n, m = 0, sum = 0;
    data v[101];
    for(int i = 0; i < 101; ++i)  // Инициализируем массив
    {
        v[i].h = i;
        v[i].c = 0;
    }
    cin >> n;
    if (n == 0) { cout << "0\n"; return 0; }  // На случай пустого ввода
    for(int i = 0, x; i < n; ++i)
    {
        cin >> x;
        if (v[x].c == 0)    // Собираем в среднее только разные высоты
        {
            sum += x;
            m++;
        }
        v[x].c++;
    }
    int avg = sum/m;      // Среднее целочисленное
    sort(v,v+101,
         [avg](const data& a, const data& b)
         {
             // Впереди - самые большие количества
             if (a.c > b.c) return true;    
             if (a.c < b.c) return false;
             // Если одинаковы - то впереди те, что ближе к среднему
             if (abs(a.h-avg) < abs(b.h-avg)) return true;
             if (abs(a.h-avg) > abs(b.h-avg)) return false;
             // Если и тут одинаковы - то с меньшими высотами
             return a.h < b.h;
         });
    cout << v[0].h << endl;
}

Из "тонкостей" - среднее считать надо целочисленно (Пятачок, похоже, тупой :)), и считать только разные высоты (но вы вроде и так это делаете...)

Дальше - все собрано в компараторе при сортировке...

READ ALSO
Ошибка PHP 500 , internal server error 500

Ошибка PHP 500 , internal server error 500

Ошибка PHP 500 , internal server error 500 Пре переходе на selectphp вылетает ошибка

196
Назначить администратором беседы ВК через API

Назначить администратором беседы ВК через API

Как назначать и разжаловать администраторов в беседах ВК через API? В Kate Mobile это реализовано только непонятно как, метода найти не могу

223
Выборка уникальных массивов из массива php

Выборка уникальных массивов из массива php

Задача стоит следующаяПолучен массив содержащий другие массивы, например:

215
Как правильно реализовывать корзину Laravel?

Как правильно реализовывать корзину Laravel?

Всем привет! Я новичок, поэтому хотелось бы услышать несколько советов

197