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
  
  */