【CSP】202006-2 稀疏向量

题目

【内容】：

思路：

思路很简单，用结构体数组存储点的位置，然后用两个for循环遍历两个向量数组，这时候问题出现了30分代码：

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

int n,a,b;
struct Point
{
	int index;
	int value;
}p[100000],p1[1000000];


int main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=a;i++)
	{
		int indexi,valuei;
		cin>>indexi>>valuei;
		p[i].index=indexi;
		p[i].value=valuei;
	}
	for(int j=1;j<=b;j++)
	{
		int indexj,valuej;
		cin>>indexj>>valuej;
		p1[j].index=indexj;
		p1[j].value=valuej;
	}
	int result=0;
	if(a<=b)
	{
		for(int i=1;i<=a;i++)
		{
			for(int j=1;j<=b;j++)
			{
				if(p[i].index == p1[j].index)
				{
					result += p[i].value*p1[j].value;
					break;
				}
			}
		}
	}
	else
	{
		for(int i=1;i<=b;i++)
		{
			for(int j=1;j<=a;j++)
			{
				if(p1[i].index == p[j].index)
				{
					result += p1[i].value*p[j].value;
					break;
				}
			}
		}
	}
	cout<<result<<endl;
}

问题：

当a,b数据值较大的时候，两个for循环会导致超时所以要用一个while或者一个for循环来处理，以及声明result的时候要用long long 型。

【100分代码】：

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

const int max_ = 5*100000+5;
int n,a,b;
struct Point
{
	int index;
	int value;
}p[max_],p1[max_];


int main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=a;i++)
	{
		int indexi,valuei;
		cin>>indexi>>valuei;
		p[i].index=indexi;
		p[i].value=valuei;
	}
	for(int j=1;j<=b;j++)
	{
		int indexj,valuej;
		cin>>indexj>>valuej;
		p1[j].index=indexj;
		p1[j].value=valuej;
	}
	long long result=0;
	int i=1,j=1;
	while((i<=a) && (j<=b))
	{
		if(p[i].index == p1[j].index)
		{
			result += p[i].value*p1[j].value;
			i++;
			j++;
		}
		if(p[i].index>p1[j].index)	j++;
		if(p[i].index<p1[j].index)	i++;
	}
	cout<<result;
	return 0;
}

PS.之前还出现了一个错误就是改了为了一个while循环以后还是出现错误，后面发现应该是空间开打了我开的是10^6，最后在全局变量那声明了max_就解决问题了。