现在的位置: 首页 > 综合 > 正文

PAT 1037. Magic Coupon

2018年01月14日 ⁄ 综合 ⁄ 共 717字 ⁄ 字号 评论关闭

题目: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;
}

来源:http://blog.csdn.net/acm_ted/article/details/20653299

抱歉!评论已关闭.