1037 Magic Coupon

948 ワード

考えてみると、ネットで検索してみると正しいので、自分で実現しました.
欲張りだと知った
またその数字<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);

}