当前位置: 代码迷 >> 综合 >> Educational Codeforces Round 50 (Rated for Div. 2) D. Vasya and Arrays(前缀和,思维)
  详细解决方案

Educational Codeforces Round 50 (Rated for Div. 2) D. Vasya and Arrays(前缀和,思维)

热度:22   发布时间:2023-11-08 15:29:43.0

题意:给出两个数组,可以合并两个数组中连续的部分,最后让两个数组完全一样,问合并后的数组的长度最长是多少。
分析:前缀和,然后模拟一下。

#include <iostream>
#define maxn 400010
typedef long long ll;
using namespace std;
ll len1,len2,cnt=0;
ll A[maxn],B[maxn];
ll dp1[maxn],dp2[maxn];int main(int argc, const char * argv[]) {std::ios::sync_with_stdio(false);cin>>len1;cin>>A[0];dp1[0]=A[0];for(int i=1;i<len1;i++){cin>>A[i];dp1[i]=A[i]+dp1[i-1];}cin>>len2;cin>>B[0];dp2[0]=B[0];for(int i=1;i<len2;i++){cin>>B[i];dp2[i]=B[i]+dp2[i-1];}if(dp1[len1-1]!=dp2[len2-1]){
   cout<<"-1"<<endl; return 0;}//solvefor(int i=0,j=0;i<len1,j<len2;i++,j++){if(dp1[i]!=dp2[j]){while(dp1[i]!=dp2[j]){if(dp1[i]>dp2[j]) j++;else i++;}}cnt++;//cout<<i<<" "<<j<<" "<<cnt<<endl;}//printcout<<cnt<<endl;return 0;
}
  相关解决方案