1 条题解

  • 0
    @ 2026-5-7 20:57:27

    简单双指针~~

    思路

    显然直接转变为正常数组暴力枚举会TLE,所以我们应善用N1,N2105N_1,N_2\leq10^5这个条件。
    大致是这样的:在循环内部定义iijj,表示枚举到两行的哪一位了。如果v1,i==v2,jv_{1,i}==v_{2,j}那么ansans就加上重复的部分,具体式子见代码。最后如果ii的位置靠后,就jj++,如果jj的位置靠后,就ii++,如果一样,就i,ji,j都++。

    AC代码

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=1e5+10;
    int a1[N],b1[N],a2[N],b2[N],l,n,m;
    signed main()
    {
    	scanf("%lld%lld%lld",&l,&n,&m);
    	for(int i=1;i<=n;i++)scanf("%lld%lld",&a1[i],&b1[i]),b1[i]=b1[i-1]+b1[i];
    	for(int i=1;i<=m;i++)scanf("%lld%lld",&a2[i],&b2[i]),b2[i]=b2[i-1]+b2[i];
    	int ans=0;
    	for(int i=1,j=1;i<=n&&j<=m;)
    	{
    		if(a1[i]==a2[j])ans+=abs(min(b1[i],b2[j])-max(b1[i-1],b2[j-1]));//printf("  %lld %lld\n",i,j);
    		if(b1[i]==b2[j])i++,j++;
    		else if(b1[i]<b2[j])i++;
    		else         j++;
    	}
    	printf("%lld\n",ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    1206
    时间
    2000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    3
    已通过
    3
    上传者