稀疏向量 CSP 202006-02 C++題解

原題連結

CSP 202006-02 稀疏向量

算法思路

為了節省空間和時間，将向量v1存儲到實體内，而對向量v2的每組資料直接判斷操作。

建立一個指向v1首元素的指針pivot。

如果目前比較的v1，v2腳标相同，則相乘，加入内積，pivot指向下一進制素。同時，這意味着前一個元素不會出現在以後的周遊中，節省了算法運作的時間。

如果v1的角标大于v2的腳标，由于v1存儲的是稀疏向量非0項元素，故對于目前輸入的v2元素，它對應的是向量V1中的零元素，故直接跳出循環，進行下一個v2元素輸入。

如果v2的腳标大于v1的角标，說明對于v2，上次輸入到本次輸入之間的區間元素都為零元素，故pivot自加一，進行下次比對。

C++代碼

//343ms    7.515MB

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	int n, a, b;
	int x, y;
	long long innerProduct = 0;
	cin >> n >> a >> b;
	vector< pair<int, int> > v1;
	for (int i = 0; i < a; i++) {
		cin >> x >> y;
		v1.push_back(make_pair(x, y));
	}
	int x1, y1;
	int pivot = 0;
	for (int j = 0; j < b; j++) {
		cin >> x1 >> y1;
		while (pivot < a) { //省時手段，如果已完成v1内元素的周遊則不進行循環
			if (v1[pivot].first == x1) { //比對成功 
				innerProduct += y1 * v1[pivot].second;
				pivot++; //進行下一個元素的比對
				break;
			}
			else if (x1 < v1[pivot].first) //目前輸入元素角标小于目前容器角标，相當于内積為0，忽略 
				break;
			else /*if (x1 > v1[pivot].first)*/ //v1目前指向元素角标小于輸入的，自加一再比較 
				pivot++; 
		}
	}
	cout << innerProduct << endl;
	return 0;
}

/*
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40
*/
           

本文思路受https://blog.csdn.net/ftimes/article/details/107527537啟發