題目
佇列法
因為是輸入是有順序的，所以直接用“先進先出”的佇列就行；
如果是無序的，那么只能用unordered_map了
#include <iostream>
#include <queue>
using namespace std;
#define _for(i,a,b) for(int i=a;i<b;i++)
struct point {
int id;
int e;
};
int main( ) {
// freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
int n,a,b;
cin>>n>>a>>b;
int y;
int x;
queue<point> q;
_for(i,0,a) {
cin>>x>>y;
q.push({x,y});
}
long long int sum=0;
_for(i,0,b) {
cin>>x>>y;
while(!q.empty()) {
int i = q.front().id , j = x;
if(i < j) {
q.pop();
} else if (i == j) {
sum+=(q.front().e * y);
q.pop();
break;
} else {
break;
}
}
}
cout<<sum;
return 0;
}
哈希表法
//這是一道簡單題
#include<iostream>
#include<map>
#define _for(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n, a, b;//維數，a,b向量的非零值個數
cin >> n >> a >> b;
map<int, int> mp;
int pos, val;
long long int sum = 0; //最終結果
_for(i,0,a) {
cin >> pos;
cin >> val;
mp[pos] = val;
}
_for(i,0,b) {
cin >> pos;
cin >> val;
if (mp[pos] != 0)
sum+= (mp[pos] * val);
}
cout << sum<< endl;
return 0;
}
快的是佇列法，空間也少
測驗樣例
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 50
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/23871.html
標籤：其他