乐趣区

PAT A1037

这道题的贪心思路就是分两个情况,一个大于零,一个小于零,分别进行排序,大的乘大的;对于代码里,我们直接对其进行 sort 排序,然后分两种情况,一个负数,一个正数;对于负数,采用的是同时两个序列从最小的开始选取,直到有一个队列穷举完毕;正数情况类似;但是需要注意的是一定要从头遍历,从而以防出现元素漏掉的情况;代码如下
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100010;
int coupon[maxn],product[maxn];
int main(){
int n,m;
scanf(“%d”,&n);
for(int i=0;i<n;i++){
scanf(“%d”,&coupon[i]);
}
scanf(“%d”,&m);
for(int i=0;i<m;i++){
scanf(“%d”,&product[i]);
}
sort(coupon,coupon+n);
sort(product,product+m);
int i=0,j,ans=0;
while(i<n&&i<m&&coupon[i]<0&&product[i]<0){
ans+=coupon[i]*product[i];
i++;
}
i=n-1;
j=m-1;
while(i>=0&&j>=0&&coupon[i]>0&&product[j]>0){
ans+=coupon[i]*product[j];
i–,j–;
}
printf(“%d\n”,ans);
system(“pause”);
return 0;
}

退出移动版