PATAdvanceLevel（甲级）1037

发表于 更新于 分类于 ， 本文字数： 4.4k 阅读时长 ≈ 4 分钟

题目链接：1037 Magic Coupon (25 分)

题目描述如下：

作者: CHEN, Yue
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
1037 Magic Coupon (25 分)
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.

Input Specification:
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 ≤10^5 , and it is guaranteed that all the numbers will not exceed 2^30.
Output Specification:
For each test case, simply print in a line the maximum amount of money you can get back.
Sample Input:
4
1 2 4 -1
4
7 6 -2 -3
Sample Output:
43

题目大意：

由于本人英语能力有限，本题并未完全读懂，以下是谷歌翻译的结果：
火星上的神奇商店提供一些魔法优惠券。每张优惠券都印有一个整数N，这意味着当您将此优惠券与产品一起使用时，您可能会获得该产品价值的N倍！更重要的是，该商店还免费提供一些奖金产品。但是，如果你对这个奖励产品申请积极N的优惠券，你将需要向商店支付N倍的奖金产品的价值……但是，嘿，神奇地，他们有一些负N的优惠券！

例如，给定一组优惠券{1 2 4 -1}，以及一组产品值{7 6 -2 -3}（以美元M $计算），其中负值对应于奖励产品。您可以将优惠券3（N为4）应用于产品1（价值M $ 7）以获得M $ 28;优惠券2到产品2获得12美元的回报;和优惠券4到产品4获得M $ 3回来。另一方面，如果您将优惠券3应用于产品4，则必须向商店支付12澳元。

每个优惠券和每个产品最多可以选择一次。你的任务是获得尽可能多的钱。
输入
第一行输入优惠劵数目Nc，接下来一行输入Nc个整数。然后下一行输入产品数量Np，接下来输入Np个整数。Nc和Np大于1小于10的5次方，所有的数小于2的30次方。
输出
对每一个测试样例在一行中输出你能拿回的最多的钱。

解题思路：

本题就是求两个集合中的数的最大乘积和。解题思路是把coupons和products进行排序，最大正数乘以最大正数，最小负数乘以最小负数，依次相乘最后结果相加就能保证得到的是最大的乘积和（舍弃乘积为负数的组合）。

本题的python解题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
nc = eval(input())
coupons = input()   #读取coupons

coupons = coupons.split(' ')    #用空格分开所有元素并把字符串型的变量变为整型变量便于排序
coupons = list(map(int, coupons))

np = eval(input())
products = input()  #读取products

products = products.split(' ')  #用空格分开所有元素并把字符串型的变量变为整型变量便于排序
products = list(map(int, products))

result = 0

coupons.sort()  #对coupons进行排序
products.sort() #对coupons进行排序

if nc > np: #以元素最少的集合作为基准进行乘积运算
    n = np
else:
    n = nc

for i in range(n):  #从前往后并从后向前双向进行正数与正数和负数与负数的乘积运算
                    #当乘积为负数时就可以停止移动了（本代码并未进行停止处理），减少运行时间
    if int(coupons[i]) < 0:
        if int(products[i]) < 0:
            result += int(coupons[i]) * int(products[i])
    if (int(products[np - i - 1]) > 0 and int(coupons[nc - i - 1]) > 0):
        result += int(coupons[nc - i - 1]) * int(products[np - i - 1])
print(result)   #输出结果

本题还用C/C++进行解题代码的编写，但同样逻辑的C代码倒数第二个测试点会运行超时
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#pragma warning(disable:4996)；
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<map>
#define N 100010
#define INIF 40000

using namespace std;

int partition(int results[], int low, int high)
{
	results[0] = results[low];

	int key = results[low];

	while (low<high)
	{
		while (low<high&&results[high] >= key)
		{
			high--;
		}
		results[low] = results[high];
		while (low<high&&results[low] <= key)
		{
			low++;
		}
		results[high] = results[low];
	}
	results[low] = results[0];
	return low;
}

void QSort(int a[], int low, int high)
{
	if (low<high)
	{
		int loc = partition(a, low, high);
		QSort(a, low, loc - 1);
		QSort(a, loc + 1, high);
	}
}

void QuickSort(int a[], int n)
{
	QSort(a, 1, n);
}


int main(void)
{
	int nc, np;
	int coupons[N], products[N];

	cin >> nc;

	for (int i = 1; i <= nc; i++)
	{
		cin >> coupons[i];
	}

	cin >> np;

	for (int i = 1; i <= np; i++)
	{
		cin >> products[i];
	}

	QuickSort(coupons, nc);
	QuickSort(products, np);

	int result = 0;

	int n = nc < np ? nc : np;
	int i, j, k;
	for ( i = 1 ; i<=n; i++)
	{
		if (coupons[i]<0 && products[i]<0)
		{
			result += coupons[i] * products[i];
		}
		else
		{
			break;
		}
	}
	for (i = 0; i<n; i++)
	{
		if (coupons[nc-i]>0 && products[np-i]>0)
		{
			result += coupons[nc-i] * products[np-i];
		}
	}

	cout << result << endl;

	system("pause");
	return 0;
}

初步排查可能是快速排序在大量数据的时候运行超时了，不过代码之后并未修改了，超时原因也有可能是其他原因，具体细节我并没有进行深入探索了。

总结

此题注意到最大正数与最大正数最小负数与最小负数相乘就可以得到结果应该就能解决了。关于C++代码排序超时的问题我还需要进行更深入的学习。

谢谢阅读，希望对你有所收获。