#include<cstdio>const int M = 500000;//a,b<=5*10^5
int u[M+1][2];//第一维是index,第二维是value
int v[M+1][2];int main(){//1.读入n,a,b//2.对数组进行遍历,如果第一位相等,将第二维相乘 int n,a,b,i;long long ans=0;scanf("%d%d%d",&n,&a,&b); //读入向量ufor(i=0;i<a;i++){scanf("%d%d",&u[i][0],&u[i][1]);} //读入向量v for(i=0;i<b;i++){scanf("%d%d",&v[i][0],&v[i][1]);}int j=0,k=0;while(j<a&&k<b){if(u[j][0]==v[k][0]){ans+=u[j][1]*v[k][1];k++;j++;}else if(u[j][0]>v[k][0]){k++;}else{j++;}} printf("%lld",ans);return 0;
}
总结:
①这里的输出结果是long long,使用printf时要用格式%lld
②典型的双指针,利用两个序列都有有序的,变O(n^2)
为O(n)
③第二次写的时候,忘记在ans加完之后加上k++;j++;
导致运行超时,还怀疑编译器出问题了,汗颜