Luogu p2141 abacus mental arithmetic test

Title Description

Abacus mental calculation is a kind of calculation technology that can complete fast calculation by simulating the change of abacus in the brain . Abacus mental arithmetic training , Can develop intelligence , It can bring a lot of convenience to our daily life , So it's popularized in many schools .

Some school's abacus mental arithmetic teacher uses a kind of quick examination abacus mental arithmetic addition ability test method . He randomly generates a set of positive integers , The numbers in the set are different , Then ask the students to answer ： How many of them , Exactly equal to the other two in the set （ Different ） Sum of the numbers ？

Recently, the teacher gave some test questions , Please help me find out .

Input format

There are two lines , The first line contains an integer n, The number of positive integers given in the test .

The second line has n A positive integer , Every two positive integers are separated by a space , A positive integer given in a test .

Output format

An integer , The answer to a test question .

I/o sample

Input #1 Copy

4
1 2 3 4

Output #1 Copy

2

explain / Tips

【 Sample explanation 】

from 1+2=3,1+3=4, So the answer to meet the test requirements is 2.

Be careful , The addend and the addend must be two different numbers in the set .

Their thinking ：

First sort all numbers , Then calculate the sum of each logarithm . Then use binary search to find whether there is this and... In the sorted array , And judge whether it is the first time , If so, count it as one .

The code is as follows ：

#include <iostream>
#include <algorithm>
using namespace std;
int n, a[110],b[110];
int find(int x)
{
	int low = 1, high = n,mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (a[mid] == x)
		{
			if (b[mid] == 0)
			{
				b[mid]++;
				return 1;
			}
			else return 0;
		}
		else if (a[mid] < x) low = mid + 1;
		else if (a[mid] > x) high = mid - 1;
	}
	return 0;
}
int main()
{
	int sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n-1; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			if (find(a[i] + a[j]))	sum++;
		}
	}
	cout << sum << endl;
	return 0;
}

zbh