The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product… but hey, magically, they have some coupons with negative N’s!
For example, given a set of coupons {1 2 4 -1}, and a set of product values {7 6 -2 -3} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.
Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.
Input Specification:
Each input file contains one test case. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here 1<= NC, NP <= 105, and it is guaranteed that all the numbers will not exceed 230.
Output Specification:
For each test case, simply print in a line the maximum amount of money you can get back.
Sample Input:
|
1 2 3 4 |
4 1 2 4 -1 4 7 6 -2 -3 |
Sample Output:
|
1 |
43 |
两序列最大正数依次相乘累加，最小负数依次相乘累加……
似乎是春节那天写的(⊙﹏⊙)
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<stdio.h> #include<stdlib.h> int compare(const void *a,const void *b) { return *(int *)b-*(int *)a; } int main() { int nc,np,i,j,*coupon,*product,temp,total=0; scanf("%d",&nc); coupon=(int *)malloc(nc*sizeof(int)); for(i=0;i<nc;i++) { scanf("%d",coupon+i); } scanf("%d",&np); product=(int *)malloc(np*sizeof(int)); for(i=0;i<np;i++) { scanf("%d",product+i); } qsort(coupon,nc,sizeof(int),compare); qsort(product,np,sizeof(int),compare); for(i=0,j=0;i<nc&&j<np;i++,j++) { temp=coupon[i]*product[j]; if(temp<=0) { break; } coupon[i]=0; product[j]=0; total+=temp; } for(i=nc-1,j=np-1;i>=0,j>=0;i--,j--) { temp=coupon[i]*product[j]; if(temp<=0) { break; } coupon[i]=0; coupon[j]=0; total+=temp; } printf("%d\n",total); } |
附带一段蠢蠢的黑历史：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
//毫不优雅的暴力穷举超时版…… //不知自己为何会突然写出这么 low 的版本 //作为黑历史留下来？还是直接删掉呢？ #include<stdio.h> #include<stdlib.h> int main() { int nc,np,*coupon,*product,i,max[2],min[2],total=0; scanf("%d",&nc); coupon=(int *)malloc(nc*sizeof(int)); for(i=0;i<nc;i++) { scanf("%d",coupon+i); } scanf("%d",&np); product=(int *)malloc(np*sizeof(int)); for(i=0;i<np;i++) { scanf("%d",product+i); } while(1) { max[0]=-1; max[1]=-1; min[0]=-1; min[1]=-1; for(i=0;i<nc;i++) { if(coupon[i]==0) { continue; } if(coupon[i]<0) { if(min[0]==-1||coupon[min[0]]>coupon[i]) { min[0]=i; } } else { if(max[0]==-1||coupon[max[0]]<coupon[i]) { max[0]=i; } } } for(i=0;i<np;i++) { if(product[i]==0) { continue; } if(product[i]<0) { if(min[1]==-1||product[min[1]]>product[i]) { min[1]=i; } } else { if(max[1]==-1||product[max[1]]<product[i]) { max[1]=i; } } } if((min[0]==-1||min[1]==-1)&&(max[0]==-1||max[1]==-1)) { break; } if(min[0]==-1||min[1]==-1) { total+=coupon[max[0]]*product[max[1]]; coupon[max[0]]=0; product[max[1]]=0; } else if(max[0]==-1||max[1]==-1) { total+=coupon[min[0]]*product[min[1]]; coupon[min[0]]=0; product[min[1]]=0; } else { total+=coupon[max[0]]*product[max[1]]; total+=coupon[min[0]]*product[min[1]]; coupon[min[0]]=0; product[min[1]]=0; coupon[max[0]]=0; product[max[1]]=0; } } printf("%d\n",total); } |