[贪心] HDU 5461 Largest Point

题意

给定一个序列,求a*ti^ti + b *tj最大值。要求(i != j).

思路

由于题目数据非常大,所以估计时间复杂度只可能为O(n),所以我们可以将a*ti^ti + b *tj分成两部分(左右两部分)分别贪心求出最大值。因为i != j,所以必须记录一下下标，然后判断,如果下标不相等，max(左部分)+max(右部分),如果相等max(max(第二大的左部分)+max(右部分),max(左部分)+max(第二大的右部分)).

代码

#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> using namespace std; typedef long long ll; const int maxn = 5000000 + 10; ll n, a, b; struct AT { ll val; int indx; bool operator< ( const AT &rhs ) { return val < rhs.val; } } at2[ maxn ], bt[ maxn ]; int main () { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int T; scanf ( "%d", &T ); for ( int ks = 1; ks <= T; ++ks ) { //用 longlong输入否则WA scanf ( "%lld%lld%lld", &n, &a, &b ); for ( int i = 0; i < n; ++i ) { ll t; scanf ( "%lld", &t ); at2[ i ].val = ll ( a * t * t ); bt[ i ].val = ll ( b * t ); //必须要保存indx at2[ i ].indx = bt[ i ].indx = i; } sort ( at2, at2 + n ); sort ( bt, bt + n ); ll ans = at2[ n - 1 ].val + bt[ n - 1 ].val; //下表要保证不相等 if ( at2[ n - 1 ].indx == bt[ n - 1 ].indx ) { ans = max ( at2[ n - 1 ].val + bt[ n - 2 ].val, at2[ n - 2 ].val + bt[ n - 1 ].val ); } printf ( "Case #%d: %lld\n", ks, ans ); } return 0; }