Решение задачи Максимизация количества нулей с Codeforces
С пояснением   Просмотров: 1291
Вы хотите создать новый массив c следующим образом: выбрать какое-то вещественное (то есть не обязательно целое) число d, и для каждого i∈[1,n] присвоить ci:=d⋅ai+bi.
Ваша задача — максимизировать количество нулей в массиве c. Чему равен максимально возможный ответ, если вы выберете значение d оптимально?
Пояснение к задаче
Давайте для каждого индекса i∈[1,n] попробуем найти такое значение d, которое сделает i-й элемент c нулем.
Если ai=0, то ci=bi, и значение d никак не влияет. Поэтому просто проигнорируем этот индекс, а в конце добавим 1 к ответу, если bi=0.
В противном случае надо выбрать d=−biai. Давайте посчитаем требуемую дробь для каждого индекса, и среди всех полученных дробей найдем ту, которая встречается наиболее часто (например, этого можно добиться, сложив все дроби в map).
Надо только научиться правильно сравнивать дроби на равенство, так как числа с плавающей точкой могут быть недостаточно точны. Давайте хранить каждую дробь как пару целых чисел (x,y), где x — числитель, а y — знаменатель. Мы должны нормализовать каждую дробь следующим образом: сначала сократим ее, найдя наибольший общий делитель x и y, а затем поделив оба числа на него. После этого проверим, что числитель неотрицательный, и если числитель не ноль, знаменатель тоже должен быть неотрицательным (можно этого добиться, умножив оба числа на −1).
Автор: Администратор