Largest Point
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=5461
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 n integers 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
HINT
题意
给你a,b，再给你n个数
然后让你求ati*ti+btj最大值是多少
题解：
我们是暴力做的，找到最大的两个数，最小的两个数，绝对值最大的两个数，绝对值最小的两个数
然后扔进一个vector里面，然后去重，然后暴力枚举的
但是还是怕tle，就分治了一下解法，数据小的话就直接n^2暴力枚举= =
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <string>
#include <ctime>
#include <list>
#include <bitset>
typedef unsigned char byte;
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.txt","r",stdin)
#define pi acos(-1) using namespace std;
const int maxn = 5e6 + ;
long long a , b , ans , p[maxn];
int vis[] , used[maxn] , n , sz;
vector<long long>s; struct data
{
long long val;
int idx;
}; data A[maxn] , B[maxn]; bool cmp1(const data & x,const data & y)
{
return x.val < y.val;
} bool cmp2(const data & x,const data & y)
{
return abs(x.val) < abs(y.val);
} void initiation()
{
scanf("%d%I64d%I64d",&n,&a,&b);
memset(used,,sizeof(int)*(n+));
for(int i = ; i < n ; ++ i)
{
scanf("%I64d",&A[i].val);
A[i].idx = i;
B[i].val = A[i].val;
B[i].idx = i;
p[i] = A[i].val;
}
s.clear();
ans = -(1LL<<);
} void dfs(int cur , long long check)
{
if(cur == ) ans = max( ans , check);
else
{
for(int i = ; i < sz ; ++ i)
{
if(!vis[i])
{
vis[i] = ;
if(cur == ) dfs(cur + , check + a * s[i]*s[i] );
else dfs(cur + , check + b*s[i]);
vis[i] = ;
}
}
}
} long long solve()
{
sort(A,A+n,cmp1);
sort(B,B+n,cmp2);
used[A[].idx] = , used[A[].idx] = , used[A[n-].idx] = , used[A[n-].idx] = ;
used[B[].idx] = , used[B[].idx] = ; used[B[n-].idx] = , used[B[n-].idx] = ;
for(int i = ; i < n ; ++ i) if(used[i]) s.push_back(p[i]);
sz = s.size();
memset(vis,,sizeof(vis));
dfs(,);
return ans;
} long long solve2()
{
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
if(i==j) continue;
ans = max(ans,A[i].val*A[i].val*a+b*A[j].val);
}
}
return ans;
} int main(int argc,char *argv[])
{
int Case;
scanf("%d",&Case);
for(int cas = ; cas <= Case ; ++ cas)
{
initiation();
printf("Case #%d: ",cas);
if(n<=) printf("%I64d\n",solve2());
else printf("%I64d\n",solve());
}
return ;
}