首页 > 试题广场 >

Magic Coupon (25)

[编程题]Magic Coupon (25)
  • 热度指数：3576 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product... but hey, magically, they have some coupons with negative N's!
For example, given a set of coupons {1 2 4 -1}, and a set of product values {7 6 -2 -3} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.
Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.

输入描述:
Each input file contains one test case.  For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers.  Then the next line contains the number of products NP, followed by a line with NP product values.  Here 1<= NC, NP <= 105, and it is guaranteed that all the numbers will not exceed 230.


输出描述:
For each test case, simply print in a line the maximum amount of money you can get back.
示例1

输入

4<br/>1 2 4 -1<br/>4<br/>7 6 -2 -3

输出

43
算法知识视频讲解
添加回答
C/C++
Myhui头像 Myhui 
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(long long a,long long b){
    return a>b;
}
long long a[100010],b[100010],sum=0;
int main(){
    int x,y;
    cin>>x;
    for(int i=0;i<x;i++) cin>>a[i];
    cin>>y;
    for(int i=0;i<y;i++) cin>>b[i];
    sort(a,a+x,cmp);
    sort(b,b+y,cmp);
    int num=0,j=0,k=0;
    while(a[j]>0&&b[k]>0&&num<=x&&num<=y){
        sum+=a[j]*b[k];
        num++;
        j++;k++;
    }
    j=x-1;k=y-1;
    while(a[j]<0&&b[k]<0&&num<=x&&num<=y){
        sum+=a[j]*b[k];
        num++;
        j--;k--;
    }
    cout<<sum;
    return 0;
}

发表于 2018-01-27 23:06:34 回复(0)
风蚀流云头像 风蚀流云 
#include<bits/stdc++.h>
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;
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%d",&c[i]);
    scanf("%d",&m);
    for(int i = 0; i < m; i++) scanf("%d",&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];
    printf("%lld\n",ans);
}

发表于 2019-04-30 15:15:12 回复(0)
刘涛201801031713506头像 刘涛201801031713506 
本题遇到的一个坑，就是int改为long long，不然会越界，如果你不写的话，pat也可以通过，这里过不了。还有一个超时的坑，一开始每次循环我都排序，然后我用了四个索引，完美解决了已经计算过的数据问题，也不会超时，只要排序一次。具体是：int cfirst = 0,clast=N1-1,pfirst=0,plast=N2-1;

#include<iostream>

#include<string>

#include<stdio.h>

#include<vector>

#include<algorithm>

using namespace std;


int main()

{

    int N1,N2;

    scanf("%d",&N1);

    long long *coupons = new long long[N1];

    for(int i=0;i<N1;i++)

    {

        long long tmp1;

        cin>>tmp1;

        coupons[i] = tmp1;

    }

    scanf("%d",&N2);

    long long *productvalue = new long long[N2];

    for(int i=0;i<N2;i++)

    {

        int tmp2;

        cin>>tmp2;

        productvalue[i]=tmp2;

    }

    long long sum = 0;

    sort(coupons,coupons+N1);

    sort(productvalue,productvalue+N2);

    int cfirst = 0,clast=N1-1,pfirst=0,plast=N2-1;

    while(1)

    {    

        if(cfirst>clast||pfirst>plast)

        {

            break;

        }

        long long maxN = coupons[clast]*productvalue[plast];

        long long minN = coupons[cfirst]*productvalue[pfirst];

        if(maxN<minN)

        {

            if(minN<=0)

            {

                break;

            }

            sum+=minN;

            cfirst++;

            pfirst++;

        }else

        {

            if(maxN<=0)

            {

                break;

            }

            sum+=maxN;

            clast--;

            plast--;

        }


    }

    cout<<sum<<endl;


    return 0;

}


发表于 2018-03-07 11:17:06 回复(0)
尤鱼哥头像 尤鱼哥 
//测试用例无问题，只是牛客的测试数据太大了。。。记得都要用long
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int az,bz;
		int m=in.nextInt();
		long a[]=new long[m];
		for(int i=0;i<m;i++){
			a[i]=in.nextLong();
		}
		int n=in.nextInt();
		long b[]=new long[n];
		for(int i=0;i<n;i++){
			b[i]=in.nextLong();
		}
		
		Arrays.sort(a);
		Arrays.sort(b);
		for(int i=0;;i++){
			if(a[i]>0){
				az=i;break;
			}
		}
		for(int i=0;;i++){
			if(b[i]>0){
				bz=i;break;
			}
		}
		long sum=0;
		for(int i=0;i<az&&i<bz;i++){
			sum+=a[i]*b[i];
		}
		for(int i=m-1,j=n-1;i>=az&&j>=bz;i--,j--){
			sum+=a[i]*b[j];
		}
		System.out.println(sum);
	}

}


发表于 2016-10-30 11:30:45 回复(0)
hustsun头像 hustsun 
#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
    int nc;
    scanf("%d", &nc);
    long long cou[100005];
    for(int i = 0; i < nc; i++){
        scanf("%lld", &cou[i]);
    }
    int np;
    scanf("%d", &np);
    long long pro[100005];
    for(int i = 0; i < np; i++){
        scanf("%lld", &pro[i]);
    }
    sort(cou, cou + nc);
    sort(pro, pro + np);
    
    long long res = 0; 
    int p = 0;
    while(p < nc && p < np && cou[p] < 0 && pro[p] < 0){
        res += cou[p] * pro[p];
        p++;
    }
    int q = np - 1;
    p = nc - 1;
    while(p >= 0 && q >= 0 && cou[p] > 0 && pro[q] > 0){
        res += cou[p] * pro[q];
        p--;
        q--;
    }
    printf("%lld", res);
    
    return 0;
}
//牛客的数据太大，全用long long，scanf也别忘了 %lld
发表于 2018-02-06 16:40:43 回复(0)
LEarBB头像 LEarBB
这个测试用例有bug吧？
发表于 2015-12-30 13:41:52 回复(5)
猫猫猫1头像 猫猫猫1 
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
	int n,m;
	long long x;
	vector<long long> v1,v2,v3,v4;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>x;
		if(x>0) {
			v1.emplace_back(x);
		} else if(x<0) {
			v2.emplace_back(x);
		}
	}
	cin>>m;
	for(int i=0; i<m; i++) {
		cin>>x;
		if(x>0) {
			v3.emplace_back(x);
		} else if(x<0) {
			v4.emplace_back(x);
		}
	}
	sort(v1.rbegin(),v1.rend());
	sort(v2.begin(),v2.end());
	sort(v3.rbegin(),v3.rend());
	sort(v4.begin(),v4.end());
	int l1=v1.size(),l2=v2.size(),l3=v3.size(),l4=v4.size();
	l1=min(l1,l3);
	l2=min(l2,l4);
	long long sum=0;
	for(int i=0;i<l1;i++){
		sum+=v1[i]*v3[i];
	}
	for(int i=0;i<l2;i++){
		sum+=v2[i]*v4[i];
	}
	cout<<sum;
	return 0;
}

发表于 2022-11-11 16:37:12 回复(0)
想去毕业旅行的猴子在泡池子头像 想去毕业旅行的猴子在泡池子
本来很简单的题 坑人的地方就在    记录最大值要用long long int 不然会溢出
发表于 2021-01-22 20:45:21 回复(0)
初心者托奇头像 初心者托奇 
a = int(input())
a = list(map(int,input().split()))
m = sorted(list(filter(lambda x:x > 0,a)),reverse = True)
n = sorted(list(filter(lambda x:x < 0,a)))
b = int(input())
b = list(map(int,input().split()))
p = sorted(list(filter(lambda x:x > 0,b)),reverse = True)
q = sorted(list(filter(lambda x:x < 0,b)))
c = 0

for i in range(min(len(m),len(p))):
    c += m[i] * p[i]
for i in range(min(len(n),len(q))):
    c += n[i] * q[i]
print(c)

发表于 2020-02-19 15:14:38 回复(0)
Khirisma头像 Khirisma

为了使和最大，正数乘正数，负数乘负数，在牛客数据比较厉害，用long long

#include<iostream>
#include<stdlib.h>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;

bool com(int a,int b) {
    return a > b;
}
int main() {
    vector<LL> con,pro;
    LL n = 0, m = 0, tem = 0, sum = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tem;
        con.push_back(tem);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> tem;
        pro.push_back(tem);
    }
    sort(con.begin(), con.end(),com);
    sort(pro.begin(), pro.end(),com);
    for (int i = 0,j = 0; i < con.size() && j < pro.size(); i++, j++) {//从开始都是正的算
        if ((con[i] > 0 && pro[j] > 0)) {
            sum += (con[i] * pro[j]);
        }
    }
    for (int i = con.size()-1, j = pro.size()-1; i >=0 && j >=0 ; i--, j--) {//从尾部都是负的算
        if (con[i] < 0 && pro[j] < 0) {
            sum += (con[i] * pro[j]);
        }
    }
    cout << sum << endl;
    system("pause");
    return 0;
}
发表于 2019-10-13 16:16:46 回复(0)
予妤。头像 予妤。 
//两个数组从小到大排序
//负数最大乘以负数最大，依次往后。
//正数最大乘以正数最大，依次向前
#include<bits/stdc++.h>
using namespace std;

int main(){
    int nc,np,i,j;
    long long c[100010],p[100010];
    long long sum=0;
    cin>>nc;
    for(i=0;i<nc;i++) cin>>c[i];
    cin>>np;
    for(i=0;i<np;i++) cin>>p[i];
    sort(c,c+nc);
    sort(p,p+np);
    i=0;j=0;
    while(c[i]<0 && p[j]<0 && i<nc && j<np) sum+=c[i++]*p[j++];
    i=nc-1;j=np-1; 
    while(c[i]>0 && p[j]>0 && i>=0 && j>=0) sum+=c[i--]*p[j--];
    cout<<sum;
    return 0;
}

编辑于 2019-02-09 19:37:40 回复(0)
无解。头像 无解。
我觉得这道题有错误，没考虑获利为正且没有优惠券时可以不用优惠券直接购买商品的情况
发表于 2018-11-30 13:00:25 回复(0)
Disconnect头像 Disconnect 
#简单来说 就是正数乘正数，负数乘负数
n = input()
n = int(n)
lst1 = list(map(int,input().split()))
lst1P,lst1N = [],[]
for i in lst1:
    if i>=0:
        lst1P.append(i)
    else:
        lst1N.append(i)
m = input()
m = int(m)
lst2 = list(map(int,input().split()))
lst2P,lst2N = [],[]
for i in lst2:
    if i>=0:
        lst2P.append(i)
    else:
        lst2N.append(i)
if lst1P:
    lst1P.sort()
    lst1P.reverse()
if lst1N:   
    lst1N.sort()
if lst2P:
    lst2P.sort()
    lst2P.reverse()
if lst2N:
    lst2N.sort()
su = 0
miP = min(len(lst1P),len(lst2P))
miN = min(len(lst1N),len(lst2N))
for i in range(0,miP):
    su+=lst1P[i]*lst2P[i]
for i in range(0,miN):
    su+=lst1N[i]*lst2N[i]   
print(su)

发表于 2018-11-27 23:14:48 回复(0)
C/C++
Caffeine头像 Caffeine 
思路： 排序后前面的乘完后，乘后面的。
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

long long HowMuch(vector<long long> & money, vector<long long> & product)
{
    long long sum = 0; 
    sort(money.begin(), money.end());
    sort(product.begin(), product.end());
    int ms=0;
    int me = money.size() - 1;
    int ps = 0;
    int pe = product.size() - 1;
    bool check = true;
    while(check)
    {
        if(ms > me || pe < ps)
        {
            break;
        }
        if(money[me] * product[pe] > 0)
        {
            sum += money[me] * product[pe];
            me--;
            pe--;
        }
        else if(money[ms] * product[ps] > 0)
        {
            sum += money[ms] * product[ps];
            ms++;
            ps++;
        }
        else
            break;
    }
    return sum;
} 


int main()
{
    int nc,np;
    //ifstream cin("test.txt");

    while(cin >> nc)
    {
        vector<long long> vc(nc);
        for(int i=0; i<nc; i++)
        {
            cin >> vc[i];
        }
        int np;
        cin >> np;
        vector<long long> vp(np);
        for(int i=0; i<np; i++)
        {
            cin >> vp[i];  
        //    cout << endl;
        }
        cout << HowMuch(vc, vp) << endl;
    }
}

发表于 2018-08-18 20:17:35 回复(0)
北海3192头像 北海3192
#include<cstdio>
#include<iostream> 
#include<algorithm>
using namespace std; 
const int maxn = 100010;
long long a[maxn] = {0};
long long b[maxn] = {0}; 
int main(){ 
int nc, np;
cin >> nc;
for(int i = 0; i < nc; i++){
cin >> a[i];
}
cin >> np;
for(int i = 0; i < np; i++){
cin >> b[i];
}
sort(a, a + nc);
sort(b, b + np);
long long sum = 0;
int i = 0;
while(i < nc && i < np && a[i] < 0 && b[i] < 0){
sum += a[i] * b[i];
i++;
}
i = nc -1;
int j = np -1;
while(i >= 0 && j >= 0 && a[i] > 0 && b[j] > 0){
sum += a[i] * b[j];
i--;
j--;
}
cout << sum;
return 0;
}
发表于 2017-02-04 22:04:24 回复(0)
jesonlin头像 jesonlin
测试用例有问题，官网都通过了
发表于 2016-02-22 16:24:15 回复(0)
必胜xiaoli头像 必胜xiaoli 
#include <iostream>
#include <vector>
#include <algorithm>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

vector<long long> coupons_P;
vector<long long> coupons_N;
vector<long long> products_P;
vector<long long> products_N;
long long maxSum = 0;
int main(int argc, char** argv) {
	int NC, NP;
	cin >> NC;
	for(int i = 0;i < NC;i++){
		long long x;
		cin >> x; 
		if(x >= 0)
		coupons_P.push_back(x);
		else
		coupons_N.push_back(x);
	}
	cin >> NP;
	for(int i = 0;i < NP;i++){
		long long x;
		cin >> x; 
		if(x >= 0)
		products_P.push_back(x);
		else
		products_N.push_back(x);
	}
	sort(coupons_P.begin(),coupons_P.end());
	sort(coupons_N.begin(),coupons_N.end());
	sort(products_P.begin(),products_P.end());
	sort(products_N.begin(),products_N.end());
	int lth1, lth2, lth3, lth4, a, b;
	lth1 = coupons_P.end() - coupons_P.begin();
	lth2 = coupons_N.end() - coupons_N.begin();
	lth3 = products_P.end() - products_P.begin();
	lth4 = products_N.end() - products_N.begin();
    a = lth1 < lth3 ? lth1 : lth3;
    b = lth2 < lth4 ? lth2 : lth4;
    for(int i = 0;i < a;i++){
    	maxSum += coupons_P[lth1 - i -1] * products_P[lth3 - i - 1];
	}
	for(int i = 0;i < b;i++){
		maxSum += coupons_N[i] * products_N[i];
	}
	cout << maxSum << endl;
	return 0;
}

发表于 2016-02-02 22:40:46 回复(1)
啥头像 啥
总体思路:
        分成正负数部分，分别点乘求和
python代码： 
def sumGroup(g1, g2):
    l1 = len(g1)
    l2 = len(g2)
    l = min(l1, l2)
    rlt = 0
    for i in range(l):
        rlt += (g1[i]*g2[i])
    return rlt

nc = input()
coupons = raw_input().strip().split()
np = input()
products = raw_input().strip().split()
coupons = map(int, coupons)
products = map(int, products)
positiveCoupons = filter(lambda x: x>=0, coupons)
negativeCoupons = filter(lambda x: x<0, coupons)
positiveProducts = filter(lambda x: x>=0, products)
negativeProducts = filter(lambda x: x<0, products)
positiveCoupons.sort(reverse = True)
positiveProducts.sort(reverse = True)
negativeCoupons.sort()
negativeProducts.sort()
rlt = sumGroup(positiveCoupons, positiveProducts)
rlt += sumGroup(negativeCoupons, negativeProducts)
print(rlt)


发表于 2016-01-24 13:11:55 回复(0)
wangtian1994头像 wangtian1994 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
	long na,nb,i,j,a[100001],b[100001],az,bz,sum=0;
	cin>>na;for(i=0;i<na;i++) cin>>a[i];
	cin>>nb;for(i=0;i<nb;i++) cin>>b[i];
	sort(a,a+na);sort(b,b+nb);
	for(i=0;i<na;i++) if(a[i]>0) break;az=i;
	for(i=0;i<nb;i++) if(b[i]>0) break;bz=i;
	for(i=na-1,j=nb-1;i>=az&&j>=bz;i--,j--) sum+=a[i]*b[j];
	for(i=j=0;i<az&&j<bz;i++,j++) sum+=a[i]*b[j];
	printf("%ld\n",sum);
	return 0;
} 

发表于 2015-09-10 22:11:46 回复(0)
提交观点

问题信息

贪心 排序
难度：
19条回答 10963浏览

热门推荐

通过挑战的用户

相关试题

Magic Coupon (25)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号