D. Vasya and Arrays

链接

[http://codeforces.com/contest/1036/problem/D]

题意

给你两个数组长度分别为n,m;

有这么一种操作，用某个数组的某个子区间元素之和代替这个子区间，这样使得数组长度减少，两个数组都可以进行

问你最后两个数组一摸一样的时候，最大数组长度是多少？如果无法使两个数组一摸一样输出-1

分析

先判断开始数组总和是否相等，不相等是不可能最后两个数组一摸一样的

从头和尾两个位置判断是否相等，相等继续如果不相等统计两个数组区间的长度，在比较大小，进行到最后

具体看代码

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=3e5+10;

ll a[N],b[N];

ll n,m;

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	//freopen("in.txt","r",stdin);

	cin>>n;

	ll sum1=0,sum2=0;

	for(int i=0;i<n;i++)

	{

		cin>>a[i];

		sum1+=a[i];

	 }

	 cin>>m;

	 for(int i=0;i<m;i++)

	 {

	 	cin>>b[i];

	 	sum2+=b[i];

	 }

	 if(sum1!=sum2){

	 	cout<<-1<<endl;

	 	return 0;

	 }

	    int cnt=0;

	 if(a[0]==b[0])

	 {

	 	int i=1,j=1;

	 	sum1=a[1],sum2=b[1];

	 	while(i<n&&j<m){

	 		if(sum1<sum2){

	 			sum1+=a[i+1];

	 			cnt++;

	 			i++;

			 }

			 else if(sum1>sum2){

			 	sum2+=b[j+1];

			 	j++;

			 }

			 else {

			 	sum1=a[i+1],sum2=b[j+1];

			 	i++,j++;

			 }

		 }

	 }

	 else if(a[n-1]==b[m-1]){

	 	int i=n-1,j=m-1;

	 	sum1=a[n-1],sum2=b[m-1];

	 	while(i>-1&&j>-1){

	 		if(sum1<sum2){

	 			sum1+=a[i-1];

	 			cnt++;

	 			i--;

			 }

			 else if(sum2<sum1){

			 	sum2+=b[j-1];

			 	j--;

			 }

			 else {

			 	sum1=a[i-1],sum2=b[j-1];

			 	i--,j--;

			 }

		 }

	 }

	 else{

	 	int i=0,j=0;

	 	sum1=a[0],sum2=b[0];

	 	while(i<n&&j<m){

	 		if(sum1<sum2){

	 			sum1+=a[i+1];

	 			cnt++;

	 			i++;

			 }

			 else if(sum1>sum2)

			 {

			 	sum2+=b[j+1];

			 	j++;

			 }

			 else {

			 	sum1=a[i+1],sum2=b[j+1];

			 	i++,j++;

			 }

		 }

	 }

	 //cout<<cnt<<endl;

	 cout<<n-cnt<<endl;

	return 0;

}

巴特西

D. Vasya and Arrays

链接

题意

分析

代码

最新文章

热门文章