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;}