1487.Problem_E

Time Limit: 1000 MS    Memory Limit: 32768 KB
Total Submission(s): 38    Accepted Submission(s): 12

Description

Woniuxia is preparing for internship. So he is bound to take a written examination and an interview. But as we all know,his level is too low. Look! The written test question stumped him again. Fortunately you couldn't stand idly by when you are beside him. Would you please to help him solve the problem as follows?

Give you a set of data,please delete three numbers among them,which can make the rest of the data is divided into four sections and the sum of each section is equal.

If it is possible,output the three deleted numbers' position in the array.

If not,output "I am done."

Input

The first line is an integer n(1 <= n <= 1000), indicating the number of the sequence.

The next line contain ai the n number (pending sequence). (0<=ai<=100000)

Output

Print the result, the three position of delete the number or “I am done.”.

Sample Input

71 1 1 1 1 1 1

Sample Output

2 4 6

Source

Unknown

                这道题的话，就是给你一堆数~~然后让取3个数字~让剩余的4个部分的和相等；

                我们可以先建立一个sum数组，表示前n个数的和是多少~~因为这个有大量的数据的区间查询。然后接一个暴力就好了~~我加了一个优先队列纯属无聊。。。。

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
int m[1005];
long long int sum[1005] = { 0 };
int main()
{
	int n;
	scanf("%d", &n);
	for (int s = 1; s <= n; s++)
	{
		scanf("%d", &m[s]);
		sum[s] = sum[s - 1] + m[s];
	}
	priority_queue<int, vector<int>, greater<int> >ans;
	int spot = 0;
	for (int s = 1; s <= n; s++)
	{
		spot=0;
		int q;
		for ( q = 1; q <= s - 1; q++)
		{
			if (2 * sum[q - 1] == sum[s - 1] - m[q]&&sum[q-1]!=0)
			{
				spot++;
				break;
			}
		}
		int p;
		for ( p = s + 1; p <= n; p++)
		{
			if (2 * (sum[p - 1] - sum[s]) == sum[n] - sum[s] - m[p]&& sum[p - 1] - sum[s]==sum[q-1])
			{
				spot++;
				break;
			}
		}
		//cout << spot << endl;
		if (spot == 2)
		{
			ans.push(s);
			ans.push(p);
			ans.push(q);
			break;
		}
	}
	if (!ans.empty())
	{
		int t = ans.top();
		ans.pop();
		printf("%d", t);
		while (!ans.empty())
		{
			printf(" %d", ans.top());
			ans.pop();
		}
		cout << endl;
	}
	else
	{
		printf("I am done.\n");
	}
	return 0;
}