首页 > 代码库 > Codeforces Round #413, rated, Div. 1 + Div. 2 C. Fountains(贪心 or 树状数组)
Codeforces Round #413, rated, Div. 1 + Div. 2 C. Fountains(贪心 or 树状数组)
http://codeforces.com/contest/799/problem/C
题意:
有n做花园,有人有c个硬币,d个钻石 (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) ,每一个花园用三个维度描述(a,b,c),分别是美丽度,所花钱币个数,钱币种类,当然,钱币之间不能兑换,该人必须要建筑两座花园,如果可以,输出两座花园总的美丽度,否则输出0;
思路:
首先想到分三种情况讨论,两个花园都用硬币,两个花园都用钻石,一个用钻石一个用硬币。
大神的代码真的是很厉害,首先买不起直接省去,接下来先按照价格对花园排序,接下来这个for_max写得很强,记录了第i个之前最大的漂亮度。,接下来进行循环,i从0开始++,然后判断是否满足i<j,然后两座花园所需钱币数量小于目前有的钱币数量,如果满足不断使i++,这样做是满足贪心要求,你目前求得必然是在当前j的条件下最大的,最终求出答案。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 12 const int maxn=100000+5;13 typedef pair<int,int> pll;14 15 int n,c,d;16 vector<pll> CC,DD;17 int for_max[maxn];18 19 int solve(vector<pll> z,int money)20 {21 int len=z.size();22 if(len<2) return 0;23 int ans=0;24 sort(z.begin(),z.end()); //先按照价格排序25 for_max[0]=0;26 for(int i=0;i<len;i++) for_max[i+1]=max(for_max[i],z[i].second); //预处理,计算出前i个当中最大的漂亮度27 int i=0;28 for(int j=len-1;j>=0;j--)29 {30 while(i<j && z[i].first+z[j].first<=money) i++; //因为for_max[i]记录了前i-1个的最大漂亮度,所以只要没超过总价格,就可以一直加上去31 i=min(i,j);32 if(i>0)33 ans=max(ans,for_max[i]+z[j].second);34 }35 return ans;36 }37 38 int main()39 {40 //freopen("D:\\input.txt","r",stdin);41 while(~scanf("%d%d%d",&n,&c,&d))42 {43 CC.clear(); DD.clear();44 int cc_max=0,dd_max=0;45 int ans=0;46 int b,p; char s[5];47 for(int i=0;i<n;i++)48 {49 scanf("%d%d%s",&b,&p,&s);50 if(s[0]==‘C‘)51 {52 if(p>c) continue; //买不起的直接省去53 CC.push_back(make_pair(p,b));54 cc_max=max(cc_max,b);55 }56 else57 {58 if(p>d) continue;59 DD.push_back(make_pair(p,b));60 dd_max=max(dd_max,b);61 }62 }63 if(cc_max!=0 && dd_max!=0) ans=cc_max+dd_max; //第一种情况64 ans=max(ans,solve(CC,c)); //两个都是硬币65 ans=max(ans,solve(DD,d)); //两个都是钻石66 printf("%d\n",ans);67 }68 return 0;69 }
另外,树状数组也是可以做的,可以参考http://blog.csdn.net/ssimple_y/article/details/71702915。
Codeforces Round #413, rated, Div. 1 + Div. 2 C. Fountains(贪心 or 树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。