【CCF CSP曆年考試帶注釋全題解 C++版】202006-2 稀疏向量

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

int main() {
	int n, a, b;
	cin >> n >> a >> b;
	vector<pair<int, int>> u; //實際上隻需要記錄一個向量
	int index, value; //由于後面反複輸入，放在外面省去每次處理空間的時間
	for (int i = 0; i < a; i++) { //輸入u向量
		cin >> index >> value;
		u.push_back(pair<int, int>(index, value));
	}
	long long result = 0; //注意取值的絕對值為10^6，乘積為10^12，必須用long long型
	int pointer = 0; //這題本質上是雙指針，但是這裡隻用了一個，因為把下面的連續輸入循環看做成指針
	for (int i = 0; pointer < a && i < b; i++) {
		cin >> index >> value;
		if (index > u[a - 1].first) break; //如果v的一個次元序号（一下簡稱v序号）比u最大的序号還大，後面就不用考慮了，乘積都為0
		while (pointer < a && index > u[pointer].first) pointer++; //如果v序号比u序号大，右移u指針直到v序号不比u大或u指針溢出
		if (pointer >= a) break; //如果u指針溢出，直接輸出結果
		if (index == u[pointer].first) result += u[pointer++].second * value; //如果序号相等，結果加上乘積，u指針右移一位
		//直接省略了v序号比u序号小的情況，因為是在循環内，以上兩種情況都不滿足直接跳到下一次輸入
	}
	cout << result;
}