BZOJ 3721 PA 2014 Final Bazarek 貪心

BZOJ 3721 PA 2014 Final Bazarek 貪心

題目大意：有n件商品，選出其中的k個，要求它們的總價為奇數，求最大可能的總價。

思路：一個O(n)的貪心，先排序，然後O(n)預處理每個節點之前出現的最大奇數和偶數，和每一個節點之後出現的最小的奇數或者偶數，之後每個詢問O(1)判斷一下。注意初值。

CODE：

#include 
#include 
#include 
#include 
#define MAX 1000010
#define INF 1e15
using namespace std;
 
int points,asks;
int src[MAX];
long long sum[MAX];
 
long long next_odd[MAX],next_even[MAX];
long long last_odd[MAX],last_even[MAX];
long long odd,even;
 
int main()
{
    cin >> points;
    for(int i = 1; i <= points; ++i)
        scanf("%d",&src[i]);
    sort(src + 1,src + points + 1);
    for(int i = points; i; --i)
        sum[i] = sum[i + 1] + src[i];
    odd = even = -INF;
    for(int i = 1; i <= points; ++i) {
        last_odd[i] = odd;
        last_even[i] = even;
        if(src[i]&1)    odd = src[i];
        else    even = src[i];
    }
    odd = even = INF;
    for(int i = points; i; --i) {
        if(src[i]&1)    odd = src[i];
        else    even = src[i];
        next_odd[i] = odd;
        next_even[i] = even;
    }
    cin >> asks;
    for(int k,i = 1; i <= asks; ++i) {
        scanf("%d",&k);
        long long temp = sum[points - k + 1];
        int p = points - k + 1;
        if(temp&1)  printf("%lld\n",temp);
        else {
            long long ans = -INF;
            ans = max(ans,temp - next_odd[p] + last_even[p]);
            ans = max(ans,temp - next_even[p] + last_odd[p]);
            if(ans < 0)  puts("-1");
            else    printf("%lld\n",ans);
        }
    }
    return 0;
}