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

451

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;
}

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

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