Largest Point

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1485 Accepted Submission(s): 588

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

3 2 1
1 2 3

5 -1 0
-3 -3 0 3 3

Sample Output

Case #1: 20
Case #2: 0

Source

2015 ACM/ICPC Asia Regional Shenyang Online

昨天输的很惨，中南地区邀请赛只A了两道题。所以感觉要多做少错思路题。

这个题分4种情况考虑，每种又分为三种情况。举一个例子：

a>0,b<0时

那么ti^2尽可能的大，tj尽可能的小。如果i！=j 那么直接取ti^2最大与tj最小。

如果i==j 那么在ti^2次大与tj最小和ti^2最大与tj次小中取大者。

还有就是 INF不能这样赋值，如1<<40 ,这个地方WA了好多次，，他会变成0

#include<stdio.h>

#include<iostream>

#include<string.h>

#include <stdlib.h>

#include<math.h>

#include<algorithm>

using namespace std;

typedef long long LL;

const LL INF = <<;

int main(){

    int tcase;

    scanf("%d",&tcase);

    int t =;

    while(tcase--){

        int n,a,b;

        scanf("%d%d%d",&n,&a,&b);

        LL ans;

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

            LL fmax = -INF,smax = -INF;

            for(int i=;i<=n;i++){

                LL num;

                scanf("%lld",&num);

                if(num>fmax){

                    smax = fmax;

                    fmax = num;

                }else{

                    smax = max(smax,num);

                }

            }

            ans = max(a*fmax*fmax+b*smax,a*smax*smax+b*fmax);

        }else if(a>&&b<){

            LL MAX=-INF,SMAX=-INF; ///平方的最大和次大

            LL MIN=INF,SMIN=INF; ///最小和次小

            int id1,id2;

            for(int i=;i<=n;i++){

                LL num;

                scanf("%lld",&num);

                LL temp = num*num;

                if(num<MIN){

                    SMIN = MIN;

                    MIN = num;

                    id1 = i;

                }else SMIN = min(SMIN,num);

                if(temp>MAX){

                    SMAX = MAX;

                    MAX  = temp;

                    id2 = i;

                }else SMAX = max(SMAX,num);

            }

            if(id1!=id2){

                ans = a*MAX+b*MIN;

            }else{

                ans = max(a*SMAX+b*MIN,a*MAX+b*SMIN);

            }

        }else if(a<&&b>){

            LL MAX = -INF,MIN = INF; ///注意这里的最小是指平方的最小

            LL smin=INF,smax = -INF; ///此处次小是指平方的次小

            int id1,id2; ///分别记录ti 和 tj 的位置

            for(int i=;i<=n;i++){

                LL num;

                scanf("%lld",&num);

                if(num>MAX) {

                    smax = MAX;

                    MAX = num;

                    id1 = i;

                }else smax = max(smax,num);

                LL temp = num*num;

                if(temp<MIN){

                    smin = MIN;

                    MIN = temp;

                    id2 = i;

                }else smin = min(smin,temp);

            }

            if(id1!=id2){

                ans = a*MIN+b*MAX;

            }

            else{

                ans = max(a*MIN+b*smax,a*smin+b*MAX);

            }

        }else {

            LL MIN = INF,SMIN = INF; ///这两个值代表绝对值次小和最小的平方

            LL MIN1 = INF,SMIN1 = INF;  ///这两个值代表次小和最小

            int id1,id2;

            for(int i=;i<=n;i++){

                LL num;

                scanf("%lld",&num);

                LL temp = num*num;

                if(num<MIN1) {

                    SMIN1 = MIN1;

                    MIN1 = num;

                    id1 = i;

                }else SMIN1 = min(SMIN1,num);

                if(temp<MIN){

                    SMIN = MIN;

                    MIN = temp;

                    id2 = i;

                }else SMIN = min(SMIN,temp);

            }

            if(id1!=id2){

                ans = a*MIN+b*MIN1;

            }else{

                ans = max(a*MIN+b*SMIN1,a*SMIN+b*MIN1);

            }

        }

        printf("Case #%d: %lld\n",t++,ans);

    }

    return ;

}

巴特西

hdu 5461(分类讨论)

Largest Point

最新文章

热门文章