微软夏令营笔试测验第一题 Array Partition

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Given an integer array A1, A2 … AN, you are asked to split the array into three continuous parts: A1, A2 … Ap | Ap+1, Ap+2, … Aq | Aq+1, Aq+2, … AN.

Let S1, S2 and S3 denote the sums of each part:

S1 = A1 + A2 + … + Ap

S2 = Ap+1 + Ap+2 + … + Aq

S3 = Aq+1 + Aq+2 + … + AN

A partition is acceptable if and only if the differences between S1, S2 and S3 (i.e. |S1 - S2|, |S2 - S3|, |S3 - S1|) are no more than 1.

Can you tell how many different partitions are acceptable?

输入
The first line contains an integer N.

The second line contains N integers, A1, A2 … AN.

For 30% of the data, N ≤ 100

For 70% of the data, N ≤ 1000

For 100% of the data, N ≤ 100000, -1000000 ≤ Ai ≤ 1000000

输出
The number of acceptable partitions.

样例解释
The three acceptable partitions are:

3 | 2 | 1 0 2

3 | 2 1 | 0 2

3 | 2 1 0 | 2

样例输入
5
3 2 1 0 2
样例输出
3

动态规划问题，按照题目的要求只有可能出现三种情况，x，x，x；x，x，x+1；x，x，x-1；很明显这三种情况是互斥的。
对于每一种情况有O(n)的算法，首先从后向前计算，用一个数组保存当前位置及之后的位置包含多少个和为sum的情况，用一个数组进行统计，之后采用从前到后遍历，遍历确定前半段的和等于固定值之后寻找跳过一个的位置存储的值（保证最少有一个划分元素），相加即可

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <string>
#include <limits.h>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stdio.h>  
using namespace std;

int *s, *x, n, c;
int res = 0;

vector<int>  cal_pos_sum(int *s,int n,int z){
    if (n <= 0)
        return vector < int > {};
    vector<int> res(n, 0);  
    if (s[n-1]==z)
        res[n - 1] = 1;
    int temp = s[n - 1];
    for (int i = n-2; i >= 0; --i)
    {
        temp += s[i];
        if (temp == z)
            res[i] = res[i + 1] + 1;
        else
            res[i] = res[i + 1];
    }
    return res;
}
int count_sum(int x,int y)
{
    vector<int> pos_sum;
    pos_sum = cal_pos_sum(s,n,y);
    int res = 0;
    int sum = 0;
    for (int i = 0; i < n - 2; ++i)
    {
        sum += s[i];
        if (sum == x){
            res += pos_sum[i + 2];
            }
        }
    return res;

}

int main()
{
    int all_sum = 0;
    int i;
    scanf_s("%d", &n);
    s = new int[n];
    for (i = 0; i<n; i++){
        scanf_s("%d", &s[i]);
        all_sum += s[i];
    }

    if ((all_sum + 1) % 3 == 0)
    {
        int out = 0;
        c = (all_sum + 1) / 3;
        out = count_sum(c,c - 1) + count_sum(c,c) + count_sum(c - 1,c);
        cout << out << endl;
    }
    else if ((all_sum - 1) % 3 == 0)
    {
        int out = 0;
        c = (all_sum - 1) / 3;
        out = count_sum(c,c + 1) + count_sum(c,c) + count_sum(c + 1,c);
        cout << out << endl;
    }
    else if ((all_sum) % 3 == 0)
    {
        int out = 0;
        c = (all_sum) / 3;
        out = count_sum(c,c);
        cout << out << endl;
    }
    else
        cout << 0 << endl;
    return 0;
}