学步园

留存map用法。

#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;

typedef struct Link
{
    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;
}