MiddleКодИногдаЕщё не отвечали
Скалярное произведение двух RLE-сжатых векторов
Два вектора целых равной логической длины заданы в RLE как списки пар (значение, количество) — напр. [4,4,5] это [(4,2),(5,1)]. Посчитайте их скалярное произведение.
Требования:
- O(|l| + |r|): идите по обоим RLE-спискам, не разворачивая их.
- Используйте 64-битный аккумулятор; вход не менять.
long long dotProduct(const std::vector<std::pair<int,int>>& l,
const std::vector<std::pair<int,int>>& r) {
// ваш код здесь
}Допишите реализацию.
Идите по обоим спискам двумя указателями, отслеживая остаток текущей серии с каждой стороны. На каждом шаге берите min(остатков) позиций, добавляя value_l * value_r * min к аккумулятору, затем двигайте исчерпанную серию. O(|l|+|r|), без разворота, 64-битная сумма.
- ✗Считать, что границы серий двух RLE совпадают, вместо потребления минимума остатков
- ✗Разворачивать векторы и терять преимущество O(|l|+|r|)
- ✗Переполнять 32-битный аккумулятор при больших произведениях value*count
- →Чем это отличается от сложения разреженных векторов, где сливают, а не умножают?
- →Почему потребление минимума двух остатков — ключевой шаг?
Оглавление
Задача
Посчитайте скалярное произведение двух RLE-векторов, не разворачивая их, за O(|l|+|r|).
Решение
#include <vector>
#include <utility>
#include <algorithm>
long long dotProduct(const std::vector<std::pair<int,int>>& l,
const std::vector<std::pair<int,int>>& r) {
long long sum = 0;
size_t i = 0, j = 0;
int leftRem = l.empty() ? 0 : l[0].second;
int rightRem = r.empty() ? 0 : r[0].second;
while (i < l.size() && j < r.size()) {
int take = std::min(leftRem, rightRem);
sum += static_cast<long long>(l[i].first) * r[j].first * take;
leftRem -= take; rightRem -= take;
if (leftRem == 0 && ++i < l.size()) leftRem = l[i].second;
if (rightRem == 0 && ++j < r.size()) rightRem = r[j].second;
}
return sum;
}Ключевые моменты
- Берём
minостатков двух серий и двигаем исчерпанную. - Без разворота — отсюда O(|l|+|r|).
- 64-битный аккумулятор защищает от переполнения.
Оглавление
