PAT甲级（12）：Magic Coupon

PAT甲级（12）：Magic Coupon

自己的思路（总会部分错误）

1、将两行数按正数从大到小排列，负数从小到大排列，这样每次就可以相同符号绝对值最大的数相乘。

2、如果遍历完一次就将两个数的flag置位false表示使用过。

#include <iostream>
#include <algorithm>
using namespace std;struct cp{int value;bool flag = true;   //true代表没用过
};
bool cmp1(cp a,cp b)
{return a.value > b.value;
}bool cmp2(cp a,cp b)
{return a.value<b.value;
}int main()
{int CN,PN,index1,index2;cin >> CN;struct cp c[CN];for(int i=0;i<CN;i++) cin >> c[i].value;sort(c,c+CN,cmp1);for(int i=0;i<CN;i++){if(c[i].value < 0){index1 = i;break;}}sort(c+index1,c+CN,cmp2);//正数从大到小排列，负数从小到大排列cin >> PN;struct cp p[PN];for(int i=0;i<PN;i++) cin >> p[i].value;sort(p,p+PN,cmp1);for(int i=0;i<PN;i++){if(p[i].value < 0){index2 = i;break;}}sort(p+index2,p+PN,cmp2);//正数从大到小排列，负数从小到大排列int maxx[100] = {0};int index= 0;int sum = 0,tmp1,tmp2;for(int i=0;i<CN;i++){int countt = 0;for(int j=0;j<PN;j++){if(c[i].value*p[j].value>0 && (c[i].flag&&p[j].flag == true)){if(c[i].value*p[j].value>maxx[index]){maxx[index] = c[i].value*p[j].value;tmp1 = i;tmp2 = j;countt++;}}}if(countt !=0){//cout << maxx[index] << " " << c[tmp1].value << " " << p[tmp2].value;c[tmp1].flag = false;p[tmp2].flag = false;index++;}}for(int i=0;i<100;i++){if(maxx[i]!=0) sum+=maxx[i];}cout << sum;return 0;
}

别人的代码(真简单。。)

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e5+10;
typedef long long LL;
int c[N],p[N];int main(){int n,m;LL ans = 0;cin >> n;for(int i = 0; i < n; i++) cin >> c[i];cin >> m;for(int i = 0; i < m; i++) cin >> p[i];sort(c,c+n),sort(p,p+m);for(int i = 0; i <n&&i<m&&c[i]<0&&p[i]<0; i++) ans += (LL)c[i]*p[i];for(int i = n-1,j = m-1; i>=0&&j>=0&&c[i]>0&&p[j]>0;i--,j--) ans += (LL)c[i]*p[j];cout << ans;
}