时间限制:
1000ms
内存限制:
65536kB
描述
度度熊拥有一个自己的Baidu空间,度度熊时不时会给空间朋友赠送礼物,以增加度度熊与朋友之间的友谊值。度度熊在偶然的机会下得到了两种超级礼物,于是决定给每位朋友赠送一件超级礼物。不同类型的朋友在收到不同的礼物所能达到的开心值是不一样的。开心值衡量标准是这样的:每种超级礼物都拥有两个属性(A, B),每个朋友也有两种属性(X, Y),如果该朋友收到这个超级礼物,则这个朋友得到的开心值为A*X + B*Y。
由于拥有超级礼物的个数限制,度度熊很好奇如何分配这些超级礼物,才能使好友的开心值总和最大呢?
输入
第一行n表示度度熊的好友个数。
接下来n行每行两个整数表示度度熊好朋友的两种属性值Xi, Yi。
接下来2行,每行三个整数ki, Ai, Bi,表示度度熊拥有第i种超级礼物的个数以及两个属性值。
1 <= n <= 1000, 0 <= Xi, Yi, Ai, Bi <= 1000, 0 <= ki <= n, 保证k1+k2 >= n
输出
输出一行一个值表示好友开心值总和的最大值
样例输入
4
3 6
7 4
1 5
2 4
3 3 4
3 4 3
样例输出
118
贪心法,每次给心情最多的一个人最好的礼物。
下面这个例子,来源于网络,就是应付样例。应该不是最终答案,密切关注正解
#include <iostream>
using namespace std;
struct Node
{
int a,b,n;
}a[2000];
struct Node2
{
int n,a,b;
}b[2];
int main()
{
int n,i,j;
long long sum = 0;
scanf("%d",&n);//好友个数
for(i=0;i<n;i++)//输入每个好友A、B属性
{
scanf("%d%d",&a[i].a,&a[i].b);
a[i].n = 0;
}
scanf("%d%d%d%d%d%d",&b[0].n,&b[0].a,&b[0].b,&b[1].n,&b[1].a,&b[1].b);
for(i=0;i<n;i++)
{
int max = -1;
int liwu = -1;
int sj = -1;
for(j=0;j<n;j++)
{
if(a[j].n==1)//已经分配礼物
continue;
int temp1 = b[0].a*a[j].a+b[0].b*a[j].b;//如果没有分配礼物,则选一个高兴值大的
int temp2 = b[1].a*a[j].a+b[1].b*a[j].b;
if(b[0].n>0&&b[1].n>0)
{
if(temp1>=temp2&&temp1>max)
max = temp1,liwu = 0,sj=j;
else if(temp2>temp1&&temp2>max)
max = temp2,liwu = 1,sj=j;
} else if(b[0].n>0) //仅有一个 还有礼物余量
{
if(temp1>max)
max = temp1,liwu = 0,sj=j;
} else if(b[1].n>0)
{
if(temp2>max)
max = temp2,liwu = 1,sj=j;
}
}
if(max!=-1&&liwu!=-1)
{
sum += max;
b[liwu].n--;
a[sj].n=1;
}
}
printf("%lld\n",sum);
return 0;
}
分享到:
相关推荐
资源名称:啊哈C语言:小学生坐在马桶上都可以读懂的C语言编程入门书资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
百度之星程序设计大赛原题 百度之星程序设计大赛已经开始报名了
百度秋招编程题之度度熊回家。代码用python编写。。。。。。
百度游戏用户洞察:热爱不息,游戏不止.pdf
本书延续了《明解C语言:入门篇》图文并茂、示例丰富、讲解细致的风格,在结构上又独树一帜,每章都会带领读者编写一个游戏程序并逐步完善或加以变更,来讲解相关的C语言进阶知识。每章的程序都很简单有趣,而且包含...
STM32百度之星算法题目部分C源码,(度度熊最近一直在陪小朋友玩,有一天,他放到桌子上的糖不见了,而屋里一共有N个小朋友,于是度度熊想知道是谁拿走了糖果,于是他就去问N个小朋友。 每个小朋友都会告诉他一句话...
百度内部SEO培训:百度网页搜索Query-Url质量评估标准
刷百度下拉框的优势: 1)展示效果最直观,最抢眼,最具价值的广告位置 2)迅速提升品牌形象和知名度,企业实力的体现 3)搜索引擎推荐结果,更具说服力,增强客户信任感 4)让客户直达你的网站,直接 跳过竞价...
通过一系列实际情形的需求,引入关于程序设计的基本知识,加上由浅入深地比较了C语言不同语法以及各种语句的区别,能够全面掌握C语言的语法特点。除此之外,本书并不仅仅着眼于入门知识讲解,对C语言在大型应用程序...
百度之星2010程序设计大赛_复赛试题:A+B问题、i-Doctor、url规范化、并行修复、猜猜你在哪儿.......
大名鼎鼎的明解c语言, 入门篇+中级篇2册 本书以C程序实例作为切入点,由浅及深,慢慢展开,较有特色,能使读者更好地理解语句和逻辑结构,
历年百度之星程序设计大赛试题题目 .
绝对完整版!百度云链接打包:HadoopSpark企业应用实战
我通过百度网盘分享的文件:考研大纲 链接:https://pan.baidu.com/s/112ALuQEFYZIBxxO-0SJfeg 提取码:6H62 复制这段内容打开「百度网盘APP即可获取」
【程序设计大赛】2018 百度之星 【程序设计大赛】2018百度之星 程序设计大赛 百度之星
百度推广优化实战:手把手教你做百度推广(下) .doc
百度副总裁王湛:百度新首页背后的营销思考.docx
原理很简单:取max1,max2 然后分别存到2个不同的数组,之后对这2个数组进行排序后比大小就可以了;
百度之星资格赛代码,我OJ了7道吧大约。