趣图在线生成网站源码,厦门北京网站建设公司哪家好,开发者社区,专业的外贸行业网站开发7-83 魔法优惠券
分数 25 全屏浏览题目
作者 陈越
单位 浙江大学
在火星上有个魔法商店#xff0c;提供魔法优惠券。每个优惠劵上印有一个整数面值K#xff0c;表示若你在购买某商品时使用这张优惠劵#xff0c;可以得到K倍该商品价值的回报#xff01;该商店还免费赠送…7-83 魔法优惠券
分数 25 全屏浏览题目
作者 陈越
单位 浙江大学
在火星上有个魔法商店提供魔法优惠券。每个优惠劵上印有一个整数面值K表示若你在购买某商品时使用这张优惠劵可以得到K倍该商品价值的回报该商店还免费赠送一些有价值的商品但是如果你在领取免费赠品的时候使用面值为正的优惠劵则必须倒贴给商店K倍该商品价值的金额…… 但是不要紧还有面值为负的优惠劵可以用真是神奇的火星
例如给定一组优惠劵面值分别为1、2、4、-1对应一组商品价值为火星币M7、6、−2、−3其中负的价值表示该商品是免费赠品。我们可以将优惠劵3用在商品1上得到M28的回报优惠劵2用在商品2上得到M12的回报优惠劵4用在商品4上得到M3的回报。但是如果一不小心把优惠劵3用在商品4上你必须倒贴给商店M12。同样当你一不小心把优惠劵4用在商品1上你必须倒贴给商店M7。
规定每张优惠券和每件商品都只能最多被使用一次求你可以得到的最大回报。
输入格式:
输入有两行。第一行首先给出优惠劵的个数N随后给出N个优惠劵的整数面值。第二行首先给出商品的个数M随后给出M个商品的整数价值。N和M在[1, 106]之间所有的数据大小不超过230数字间以空格分隔。
输出格式:
输出可以得到的最大回报。
输入样例:
4 1 2 4 -1
4 7 6 -2 -3
代码分享 #include iostream
#include algorithm
using namespace std;
int s1[1000100]{0};//优惠券的负数
int s2[1000100]{0};//优惠券的正数
int w1[1000100]{0};//价钱的负数
int w2[1000100]{0};//价钱的正数
int main(){int n,m,sum0;int a10,a20,b10,b20;cinn;for(int i0;in;i){int z;cinz;if(z0){s1[a1]z;a1;}else{s2[a2]z;a2;}}//输入每张优惠券的数额cinm;for(int i0;im;i){int z;cinz;if(z0){w1[b1]z;b1;}else{w2[b2]z;b2;}}//输入每件商品的价格sort(s1,s1a1);//把优惠券的负数从小到大排序sort(s2,s2a2,greaterint());//优惠券的正数从大到小排列sort(w1,w1b1);//把商品的价格的负数从小到大排序sort(w2,w2b2,greaterint());//把商品的价格的正数从大到小排序for(int i0;ia1ib1;i){sums1[i]*w1[i];}//计算负数的值for(int j0;ja2jb2;j){sums2[j]*w2[j];}//计算正数的值coutsum;return 0;
}
