Largest Point

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 3065 Accepted Submission(s): 1078

Problem Description

Given the sequence

Input

An positive integer

Output

The output contains exactly

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

Source

题意：

　　求a*ti*ti+b*tj的最大值，ti，tj是num数组里的两个数

分析：

　　分情况考虑a和b为正为负的情况，当a，b为正时ti，tj要尽量大，因为a*ti*ti的影响大于b*tj，所以ti优先取最大值，在ti取完最大值后tj再来取剩下的最大值（这里用个map判断是否还剩余最大值，最大值可能有多个或者ti取了负的最大值）

　　然后是为负的情况用同样的方法计算就行

#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define debug(a) cout << #a << " " << a << endl#define inf 0x17a6e6736e9using namespace std;const int maxn = 5*1e6 + 10;const int mod = 1e9 + 7;typedef long long ll;ll s1[maxn], s2[maxn];int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll T, t = 0; cin >> T; while( T -- ) { t ++; ll n, a, b; cin >> n >> a >> b; map
                 
                   mp; for( ll i = 0; i < n; i ++ ) { cin >> s1[i]; s2[i] = abs(s1[i]); mp[s1[i]] ++; } sort( s2, s2+n ); sort( s1, s1+n ); ll sum = 0; if( a > 0 ) { sum += a*s2[n-1]*s2[n-1]; if( b > 0 ) { if( mp[-s2[n-1]] ) { mp[-s2[n-1]] --; } else { mp[s2[n-1]] --; } if( mp[s1[n-1]] > 0 ) { sum += b*s1[n-1]; } else { sum += b*s1[n-2]; } } else if( b < 0 ) { if( mp[s2[n-1]] ) { mp[s2[n-1]] --; } else { mp[-s2[n-1]] --; } if( mp[s1[0]] > 0 ) { sum += b*s1[0]; } else { sum += b*s1[1]; } } } else if( a < 0 ) { sum += a*s2[0]*s2[0]; if( b > 0 ) { if( mp[-s2[0]] ) { mp[-s2[0]] --; } else { mp[s2[0]] --; } if( mp[s1[n-1]] > 0 ) { sum += b*s1[n-1]; } else { sum += b*s1[n-2]; } } else if( b < 0 ) { if( mp[s2[0]] ) { mp[s2[0]] --; } else { mp[-s2[0]] --; } if( mp[s1[0]] > 0 ) { sum += b*s1[0]; } else { sum += b*s1[1]; } } } cout << "Case #" << t << ": " << sum << endl; } return 0;}

转载于:https://www.cnblogs.com/l609929321/p/9398505.html

你可能感兴趣的文章