Codeforces 1006C：Three Parts of the Array（前缀和+map）

题目链接：http://codeforces.com/problemset/problem/1006/C

（CSDN又改版了，复制粘贴来过来的题目没有排版了，好难看，以后就截图+题目链接了）

题目截图：

题意：一个长度为n的数组，按顺序分成三部分，要求第一部分和第三部分元素的和相等（每一部分都可以没有元素，没有元素的部分元素和为0），求出第一部分和第三部分最大的相等的元素和，如果没有输出0

实现：开两个数组记录下数组的前缀和，后缀和（不知道这样叫对不对），然后用map记录下每个前缀和，后缀和指向的位置，用vis对后缀和的元素标记，然后利用vis查找前缀和中是否有和后缀和相同的位置，并且比较这两个位置的大小，如果前缀和的位置小于后缀和的位置，更新ans的值，否则停止循环

（说的好乱，完全不知道在说什么，以上废话自动忽略直接看代码吧，请自动忽略代码中的注释）

还有vis标记要用map标记！！！不要用数组，数太大，超范围了！！！

AC代码：

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#define ll long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x3f3f3f3f

const double E=exp(1);

const int maxn=1e6+10;

using namespace std;

ll a[maxn],b[maxn];

ll first[maxn],last[maxn];//前缀和，后缀和

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	map<ll,int>mmp;//标记前缀和的位置

	map<ll,int>mmmp;//标记后缀和的位置

	map<ll,int>vis;//记录后缀和是否出现

	vis.clear();

	ll n;

	cin>>n;

	ms(first);

	ms(last);

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

	{

		cin>>a[i];

		first[i]=first[i-1]+a[i];

		mmp[first[i]]=i;//第i个数的前缀和指向i

		b[n-i+1]=a[i];//翻转a数组，存入b中

	}

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

	{

		last[i]=last[i-1]+b[i];

		mmmp[last[i]]=n-i+1;

		vis[last[i]]=1;//记录下后缀和，

	}

	ll ans=0;

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

	{

		if(vis[first[i]])//如果第i个数的前缀和在last中出现过

		{

			int x=mmp[first[i]];

			int y=mmmp[first[i]];

			if(x<y)//如果first和last数组无重叠元素

			{

				ans=max(ans,first[i]);

			}

			else

				break;

		}

	}

	cout<<ans<<endl;

	return 0;

}