1 条题解
-
0
简单双指针~~
思路
显然直接转变为正常数组暴力枚举会TLE,所以我们应善用这个条件。
大致是这样的:在循环内部定义和,表示枚举到两行的哪一位了。如果那么就加上重复的部分,具体式子见代码。最后如果的位置靠后,就++,如果的位置靠后,就++,如果一样,就都++。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
- 上传者