Largest Point

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 1102 Accepted Submission(s): 429

Problem Description

Given the sequence A with n integers t1,t2,⋯,tn.
Given the integral coefficients a and b.
The fact that select two elements ti and tj of A and i≠j to
maximize the value of at2i+btj,
becomes the largest point.

Input

An positive integer T,
indicating there are T test
cases.

For each test case, the first line contains three integers corresponding to n (2≤n≤5×106), a (0≤|a|≤106) and b (0≤|b|≤106).
The second line contains nintegers t1,t2,⋯,tn where 0≤|ti|≤106 for 1≤i≤n.

The sum of n for
all cases would not be larger than 5×106.

Output

The output contains exactly T lines.

For each test case, you should output the maximum value of at2i+btj.

Sample Input

2

3 2 1

1 2 3

5 -1 0

-3 -3 0 3 3

Sample Output

Case #1: 20

Case #2: 0

题意给了a b的两个值，然后给了一大堆t的值，问在这些t的值里面求最大的 at2i+btj.

分情况讨论，对于a大于零小于零，b大于零小于零。然后记录最大值次大值最小值次小值还有一个绝对值最小值，这五个值就够用了。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

long long test, n, a, b;

long long i, j;

long long abs_min, max1, max2, min1, min2;

int main()

{

	long long temp;

	cin >> test;

	for (i = 1; i <= test; i++)

	{

		abs_min = 1000005;

		max1 = -1000005;

		max2 = -1000005;

		min1 = 1000005;

		min2 = 1000005;

		cin >> n >> a >> b;

		for (j = 1; j <= n; j++)

		{

			scanf("%lld",&temp);

			if (abs(temp) < abs_min)

			{

				abs_min = abs(temp);

			}

			if (temp > max1)

			{

				max2 = max1;

				max1 = temp;

			}

			else if (temp > max2)

			{

				max2 = temp;

			}

			if (temp < min1)

			{

				min2 = min1;

				min1 = temp;

			}

			else if (temp < min2)

			{

				min2 = temp;

			}

		}

		long long res;

		if (a >= 0 && b>=0)

		{

			res = a*max1* max1 + b*max2;

			res = max(res, a*min1 * min1 + b*max1);

		}

		else if (a >= 0 && b <= 0)

		{

			res = a*max1 * max1 + b*min1;

			res = max(res, a*min1 * min1 + b*min2);

		}

		else if (a <= 0 && b <= 0)

		{

			if (min1 == abs_min)

			{

				res = a*abs_min*abs_min + b*min2;

			}

			else

			{

				res = a*abs_min*abs_min + b*min1;

			}

		}

		else

		{

			if (max1 == abs_min)

			{

				res = a*abs_min*abs_min + b*max2;

			}

			else

			{

				res = a*abs_min*abs_min + b*max1;

			}

		}

		cout << "Case #"<<i<<": "<<res<< endl;

	}

	return 0;

}

巴特西

HDU 5461：Largest Point

Largest Point

最新文章

热门文章