ЕГЭ C4 (C++)

[0x44616E69696C]

http://scool4.zxq.net/Q/

Вот, попробовал, не работает.

Сначала выводит 1 без ключа, потом выводит не все что должна.
Почему программа себя так ведет? Можно ли такое решение, даже рабочее назвать "эффективным"?
Может есть идеи?
И заодно, если не сложно, посоветуйте книжку по алгоритмам в общем, составление, оптимизация.

[ep1a]

0x44616E69696C, я в свое время решал много вариантов ЕГЭ, и потом без проблем его сдал, он несложный. Еще лазил по всяким форумам и сайтам, видел всякие красивые методы решения различных задач. Также есть сайты со списком задач - можно их туда же отправлять на проверку - пример: acmp.ru

[Abstraction]

1)

for (int i=0; i<=N; i++)//тут я думаю все понятно.

Мне непонятно. Цикл отработает N+1 раз.
2) else-ветка вывода мне непонятна совершенно. Почему бы тупо не вывести первые три фирмы, а дальше выводить фирмы, пока частота их упоминания равна частоте упоминания третьей?

Можно ли такое решение, даже рабочее назвать "эффективным"?

Да, вполне.

[rrrFer]

Почему бы тупо не вывести первые три фирмы, а дальше выводить фирмы, пока частота их упоминания равна частоте упоминания третьей?

потому что фирмы в мапе у него упорядочены по алфавиту, но не по частоте.
Тут нет решения, эффективным называть нечего. В ветке else какие-то отстои.

for (int k = 1, counter = 0;counter<3; k++)//цикл по числам от 1
                {
                        for (f=firm.begin(); f!=firm.end(); f++)//обход map f -- итератор, см. выше.
                        {
                                if((*f).second==k) //сравниваем все числовые данные map с текущим

Вы берете все k от 1 до черт знает чего и ищите это к в map - это ужасно. Тут сложность даже не O(n^2).

Т.е. если у меня есть всего 4 фирмы и каждая из них встречается 1000 раз - будет 3 * 1000 * 4 итераций внутреннего цикла в худшем случае (тут не должно быть более 3*4 итераций)

Поиск наибольшего элемента массива - O(n)
Если вы выполните такой поиск 3 раза -алгоритм будет не самым оптимальным, но значительно лучше вашего.

Можно все значения засунуть в еще один мап и дальше сделать как абстракшн советует, но это будет неоптимально по памяти (там в требованиях про это написано).

[Abstraction]

Сообщение от rrrFer

потому что фирмы в мапе у него упорядочены по алфавиту, но не по частоте.

/me идиот. Да, карта упорядочивает по ключу, что даёт нам быстрый поиск названий. Под занавес надо переупорядочить по значениям -

bool ComparePairs(std::pair<std::string, int> a, std::pair<std::string, int> b){
  return a.second() < b.second();
}
//...
std::vector< std::pair<std::string, int> > sorted (firm.begin(), firm.end());
std::sort(sorted.begin(), sorted.end(), ComparePairs);

[0x44616E69696C]

бррр.. задолбало: переписал, в первом цикле изменил условие на

for (int i=0; i<N; i++)

отрабатывает N-1 раз, я не понимаю. А функция Out первый раз всегда выводит просто единицу, но мне непонятно откуда она берется.

[rrrFer]

А функция Out первый раз всегда выводит просто единицу, но мне непонятно откуда она берется.

ставишь точку останова в Out, выполняешь программу до нее, смотришь на значения которые она выводит и пытаешь догадаться ) если не получается - выполняй программу по шагам от начала до тех пор, пока единицу не выведет.

Под занавес надо переупорядочить по значениям -

можно конешно, но сортировка всего списка - это долго. Этож не просто так задача, а часть "С" ЕГЭ xD.
Я думаю, решить ее можно за линейное время )

переписал

Выше тебе советовали выкинуть map, пользы тебе от него не будет

-------добавил:

Держи вот кусок кода:

#include <fstream>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
int main() {
  const int NNUM = 3;
  std::multiset<std::string> set;
  std::ifstream ifst("input.txt");
  int v[NNUM] = {0}, num, n;
  
  auto change = [&v](int val) {
    auto t = std::min_element(v, v + NNUM);
    if (*t < val) (*t) = val;
  };
  
  ifst >> n; ifst.get();
  for (int i = 0; i < n; ++i) {
    const int LEN = 64;
    char cbuff[LEN];
    ifst.getline(cbuff, LEN);
    set.insert(cbuff);
  }
  ifst.close();
  
  std::string buff = *set.begin();
  num = 0;
  for (auto t : set) {
    if (t == buff)
      ++num;
    else {
      change(num);
      num = 1;
      buff = t;
    }
  }
  change(num);
  
  for (auto t : v)
    std::cout << t << std::endl;
}

за линейное время рассчитывается 3 наибольших значения количества вхождения слов с файла.
Тебе остается в еще одном цикле вывести значения, которые встречаются заданное число раз (число то уже известно) - это тоже можно сделать за линейное время, почти также.
Сложность алгоритма останется линейной.

[0x44616E69696C]

Выше тебе советовали выкинуть map, пользы тебе от него не будет

Понял, я упустил значительную деталь в описании. Надо чтобы рядом с названием выводилось кол-во упоминаний.

Держи вот кусок кода:

Спасибо! C++ 11 --- это круто, всю ночь изучал нововведения, понял что мой учебник STL протух. Кстати, на JavaScript похоже.

[rrrFer]

Понял, я упустил значительную деталь в описании. Надо чтобы рядом с названием выводилось кол-во упоминаний.

но решение выше это не портит. Тебе надо дописать цикл, очень похожий на тот, в котором вычисляется массив v. там ты также должен будешь рассчитывать num (абсолютно также как это делается в примере) и если в массиве v есть значение num - то выводишь строку (в примере это переменная t), (а num в этом случае и есть то самое " кол-во упоминаний.").