HDU 5461 – Largest Point [枚举+贪心]

点击打开HDU题目链接

题意

给你一个数列v和a,b,在数列中找两个不同位置的数vi,vj,求a*vi*vi+b*vi的最大值

分析

先对数列排序,枚举i,然后贪心求出j,此时的j要么是数列最大值,要么是数列最小值。注意最后的结果可能会超出int

C++代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5120000;
int n, kase;
ll a, b, v[maxn];

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%lld%lld", &n, &a, &b);
        for(int i = 1; i <= n; ++i)
            scanf("%lld", v + i);
        sort(v + 1, v + n + 1);
        ll best = a * v[1] * v[1] + b * v[2];
        for(int i = 1; i <= n; ++i) {
            ll cur = a * v[i] * v[i];
            if(i == 1) best = max(best, cur + max(b * v[2], b * v[n]));
            else if(i == n) best = max(best, cur + max(b * v[1], b * v[n-1]));
            else best = max(best, cur + max(b * v[1], b * v[n]));
        }
        printf("Case #%d: %lld\n", ++kase, best);
    }
    return 0;
}

欢迎留言