HDU 5461 Largest Point 【思维】

发表于 | 更新于 | 分类于

题目大意：

现在有n个点，给出a和b，从这n个点中选出不同的两个点x、y，使得$ax ^ 2 + by$最大。问最大值是多少。

解题思路：

首先想到的是找出最大值和最小值来，分4种情况讨论：

  1. a > 0 && b > 0

  2. a > 0 && b < 0

  3. a < 0 && b > 0

  4. a < 0 && b < 0

分成这样后发现需要找的还有次大值、次小值以及最接近0的那个值。然后当最大值或最小值和最接近0的值是同一个时还要再进行判断。到这里有点晕了。。

后来发现一种很巧妙的思路，就是用两个数组存一下$ax^2$$和$$bx$的值，然后将两者排序，直接取两者的最大值就行了。当两者的最大值用的是同一个x后再加个比较就行了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5000010;

int t, n, x;
long long a, b, res;
struct node
{
    int idx;
    long long val;
} A[N], B[N];
bool cmp(node u, node v)
{
    return u.val < v.val;
}
int main()
{
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        scanf("%d%lld%lld", &n, &a, &b);
        for(int i= 1; i <= n; ++i)
        {
            scanf("%d", &x);
            A[i].val = a * x * x;
            B[i].val = b * x;
            A[i].idx = B[i].idx = i;
        }
        sort(A + 1, A + 1 + n, cmp);
        sort(B + 1, B + 1 + n, cmp);
        if(A[n].idx == B[n].idx)
            res = max(A[n].val + B[n - 1].val, A[n - 1].val + B[n].val);
        else
            res = A[n].val + B[n].val;
        printf("Case #%d: %lld\n", cas, res);
    }
    return 0;
}
Donate comment here
0%