首页 > 代码库 > BZOJ 3721 PA 2014 Final Bazarek 贪心
BZOJ 3721 PA 2014 Final Bazarek 贪心
题目大意:有n件商品,选出其中的k个,要求它们的总价为奇数,求最大可能的总价。
思路:一个O(n)的贪心,先排序,然后O(n)预处理每个节点之前出现的最大奇数和偶数,和每一个节点之后出现的最小的奇数或者偶数,之后每个询问O(1)判断一下。注意初值。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #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; }
BZOJ 3721 PA 2014 Final Bazarek 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。