1037 Magic Coupon
948 ワード
考えてみると、ネットで検索してみると正しいので、自分で実現しました.
欲張りだと知った
またその数字<2^30を考慮する必要はありません
欲張りだと知った
またその数字<2^30を考慮する必要はありません
#include <stdio.h>
#include <algorithm>
#define len 100000+5
int NC, NP;
int c[len],p[len];
int cmp(const void * a, const void * b){// cmp
return (*(int*)a - *(int *)b);
}
int main(){
//freopen("in.txt","r",stdin);
scanf("%d",&NC);
for(int i = 0 ; i < NC; i++){
scanf("%d",&c[i]);
}
scanf("%d",&NP);
for(int i = 0 ; i < NP; i++){
scanf("%d",&p[i]);
}
qsort(c,NC,sizeof(int),cmp);
qsort(p,NP,sizeof(int),cmp);
long long res = 0;
for(int i = NC-1, j = NP-1; i >= 0 && j >= 0; i--,j--){
if(c[i]>0 && p[j]>0){
res += c[i]*p[j];
}
}
for(int i =0, j = 0; i < NC && j < NP; i++,j++){
if(c[i]<0 && p[j]<0){
res += c[i]*p[j];
}
}
printf("%lld",res);
}