## HOJ 13013 Triangles（map）

2019年02月12日 ⁄ 综合 ⁄ 共 954字 ⁄ 字号 评论关闭

```#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>

using namespace std;

const int maxn = 1e5 + 10;
const int plu = 1e3 * maxn;

{
int lb, rb, pos;
Link(int _lb = 0, int _rb = 0, int _pos = 0):
lb(_lb), rb(_rb), pos(_pos) {}
}ll;

ll p[maxn];

int main()
{
//freopen("F.in", "r", stdin);

int n, sum, tmp, ans;
while(~scanf("%d", &n))
{
sum = ans = 0;
map<int, int> len;
map<int, int>::iterator ita;
map<int, int>::iterator itb;
for(int i = 0; i < n; i++)
{
len[sum] = i;
p[i].pos = sum;
scanf("%d", &tmp);
sum += tmp;
p[i].lb = (i - 1 + n) % n;
p[i].rb = (i + 1 + n) % n;
}
if(sum % 3)
printf("0\n");
else
{
int now = 0;
while(p[now].rb != now)
{
int p1, p2, p3;
p1 = p[now].pos;
p2 = (p[now].pos + sum / 3) % sum;
p3 = (p[now].pos + sum * 2 / 3) % sum;
if(p1 < p2 && p2 < p3)
{
ita = len.find(p2);
itb = len.find(p3);
if(ita != len.end() && itb != len.end())
{
ans++;
p[p[now].lb].rb = p[now].rb;
p[p[len[p2]].lb].rb = p[len[p2]].rb;
p[p[len[p3]].lb].rb = p[len[p3]].rb;
}
}
if(now < p[now].rb)
now = p[now].rb;
else
break;
}
printf("%d\n", ans);
}
}
return 0;
}```