题目:http://pat.zju.edu.cn/contests/pat-a-practise/1037
题解:
有种优惠卷,使用后可以获得相应商品价格x的n倍的的金额,但n和x都可能为负数,乘积为负就要付出对应金额。
解法就是把商品价格和优惠卷都按从小到大排序,正的和正的相乘,负的和负的相乘。
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff int a[100005],b[100005]; int main() { int n,m,summ=0; scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d",a+i); scanf("%d",&m); for(int i=0;i<m;++i) scanf("%d",b+i); sort(a,a+n); sort(b,b+m); for(int i=0;i<n&&i<m;++i) if(a[i]<0&&b[i]<0) summ+=(a[i]*b[i]); for(int i=n-1,j=m-1;i>=0&&j>=0;--i,--j) if(a[i]>0&&b[j]>0) summ+=(a[i]*b[j]); printf("%d\n",summ); return 0; }