CSP 202006-2 稀疏向量-有解無憂

題目鏈接：稀疏向量
題目描述
分析
- 稀疏向量求內積，可以先把輸入存到兩個容器中，然后雙指標遍歷求和，復雜度O(n)
- 一開始想得很簡單，用一對資料用pair存，用vector<pair<int,int>>存一個向量，然后遍歷就行了，可以滿分
- 后來看了看別人的解法，發現我這樣做默認了輸入的index升序，但題中沒說明，所以改用map做了，可以自動升序
- 還有一點是這題容易超時，限時2s，vector做用時1.963s，map做直接超時只有60分，優化C++的輸入輸出后可以滿分，用時不到1.5s

vector解法（默認輸入index升序）

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

vector<pair<int,int>> A,B;

int  main()
{
	int n,a,b;
	cin>>n>>a>>b;
	
	int pos,value;
	for(int i=0;i<a;i++)
	{
		cin>>pos>>value;
		A.push_back(make_pair(pos,value));
	} 
	for(int i=0;i<b;i++)
	{
		cin>>pos>>value;
		B.push_back(make_pair(pos,value));
	}
		
	int i1=0,i2=0;
	int pa,pb,va,vb;
	long long sum = 0;
	
	pa = A[i1].first;	va = A[i1].second;	i1++;
	pb = B[i2].first;	vb = B[i2].second;	i2++;
	while(1)
	{
		if(pa == pb)
		{
			//cout<<"add:"<<va<<" "<<vb<<endl;
			sum += va*vb;
			
			if(i1 == A.size() || i2==B.size())	break; 
			
			pa = A[i1].first;	va = A[i1].second;	i1++;
			pb = B[i2].first;	vb = B[i2].second;	i2++;
		}
		else if(pa<pb)
		{
			if(i1 == A.size())	break; 
			pa = A[i1].first;	va = A[i1].second;	i1++;
		}	
		else
		{
			if(i2 == B.size())	break; 
			pb = B[i2].first;	vb = B[i2].second;	i2++;
		}			 
	}
	
	cout<<sum<<endl;
	
	return 0;
}

map解法（注意輸入輸出優化）

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

map<int,int> A;
map<int,int> B;

int  main()
{
	//C++輸入輸出優化 
	ios::sync_with_stdio(0);
	cin.tie(0);	cout.tie(0); 
	
	int n,a,b;
	cin>>n>>a>>b;
	
	int pos,value;
	for(int i=0;i<a;i++)
	{
		cin>>pos>>value;
		A[pos] = value; 
	} 
	for(int i=0;i<b;i++)
	{
		cin>>pos>>value;
		B[pos] = value; 
	}
		
	int pa,pb,va,vb;
	long long sum = 0;
	
	map<int,int>::iterator ita=A.begin(),itb=B.begin();
	pa = ita->first;	va = ita->second; 	ita++;
	pb = itb->first;	vb = itb->second;	itb++;	

	while(1)
	{
		if(pa == pb)
		{
			//cout<<"add:"<<va<<" "<<vb<<endl;
			sum += va*vb;
			
			if(ita == A.end() || itb == B.end())	break; 
				
			pa = ita->first;	va = ita->second;	ita++;
			pb = itb->first;	vb = itb->second;	itb++;
		}
		else if(pa<pb)
		{
			if(ita == A.end())	break; 
			pa = ita->first;	va = ita->second;	ita++;
		}		 
		else
		{
			if(itb == B.end())	break; 
			pb = itb->first;	vb = itb->second;	itb++;
		} 
	}		
	
	cout<<sum<<endl;
	
	return 0;
}
/*
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40

*/

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/25580.html

標籤：其他

上一篇：uniapp滑塊驗證和依次點擊字體驗證（包含vue，后端，html端，weex，reactnative，android，ios等多端）

下一篇：移動端-安卓-介面測驗簡介