HDU 5461：Largest Point

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