102896: [Atcoder]ABC289 G - Shopping in AtCoder store
Description
Score : $600$ points
Problem Statement
Takahashi runs AtCoder store. $N$ customers visit the store, and $M$ items are sold in the store. The motivation of the $i$-th $(1\leq i\leq N)$ customer is $B _ i$. The value of the $j$-th $(1\leq j\leq M)$ item is $C _ j$.
Takahashi sets a price for each item. The $i$-th customer buys one $j$-th item if and only if its price $P _ j$ satisfies:
- $B _ i+C _ j\geq P _ j$.
For each $j=1,2,\ldots,M$, find the gross sale of the $j$-th item when Takahashi sets the price so that the sale is maximized. The gross sale of the $j$-th item is defined as the product of $P _ j$ and the number of customers that buys the $j$-th item.
Constraints
- $1\leq N\leq2\times10^5$
- $1\leq M\leq2\times10^5$
- $0\leq B _ i\leq10^9\quad(1\leq i\leq N)$
- $0\leq C _ i\leq10^9\quad(1\leq i\leq M)$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $B _ 1$ $B _ 2$ $\ldots$ $B _ N$ $C _ 1$ $C _ 2$ $\ldots$ $C _ M$
Output
Print a line containing the gross sale of the $j$-th item for each $j=1,2,\ldots,M$, separated by spaces.
Sample Input 1
5 4 100 200 300 400 500 120 370 470 80
Sample Output 1
1280 2350 2850 1140
For example, he may set the price of the $1$-st item to $320$; then the $2$-nd, $3$-rd, $4$-th, and $5$-th customers will buy one. The gross sale of the $1$-st item will be $1280$. Since he cannot make the gross sale of the $1$-st item greater than $1280$, the $1$-st value to be printed is $1280$.
Sample Input 2
4 4 0 2 10 2 13 13 0 4
Sample Output 2
52 52 10 18
Two customers may have the same motivation. Also, two items may have the same value.
Sample Input 3
12 15 16 592 222 983 729 338 747 61 451 815 838 281 406 319 305 519 317 590 507 946 365 5 673 478 340 176 2
Sample Output 3
6280 5466 5382 7410 5454 8120 7290 11680 5870 3670 8950 7000 5620 4608 3655
Sample Input 4
5 5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 4
10000000000 10000000000 10000000000 10000000000 10000000000
Note that the gross sales may not fit into a $32$-bit integer type.
Input
题意翻译
给定 $N$ 位顾客，$M$ 件商品，每位顾客有一个购买意向 $B_i$，每一件商品有一个价值 $C_i$。 设定每个商品的价格为 $P_i$，一个顾客 $i$ 会买一个商品 $j$ 当且仅当 $B_i + C_j \ge P_j$。 对于每一个商品，设置价格 $P_i$ 使销售额最大（销售额等于价格乘以购买人数），输出销售额。 - $1 \le N, M \le 2 \times 10^5$； - $0 \le B_i , C_i \le 10^9$。Output
分数：$600$分
问题描述
高桥经营着一家AtCoder商店。有$N$位顾客光顾这家店，商店内有$M$件商品。 第$i$位顾客（$1\leq i\leq N$）的购买动力为$B _ i$。 第$j$件商品（$1\leq j\leq M$）的价值为$C _ j$。
高桥为每件商品设定了价格。 如果第$i$位顾客购买第$j$件商品的价格$P _ j$满足以下条件，则该顾客会购买该商品：
- $B _ i+C _ j\geq P _ j$。
当高桥设定价格时，对于每一件商品$ j=1,2,\ldots,M$，请找出该商品的最大销售额。 第$j$件商品的销售额定义为$P _ j$与购买该商品的顾客数量的乘积。
限制条件
- $1\leq N\leq2\times10^5$
- $1\leq M\leq2\times10^5$
- $0\leq B _ i\leq10^9\quad(1\leq i\leq N)$
- $0\leq C _ i\leq10^9\quad(1\leq i\leq M)$
- 输入中的所有值均为整数。
输入
输入通过标准输入以以下格式给出：
$N$ $M$ $B _ 1$ $B _ 2$ $\ldots$ $B _ N$ $C _ 1$ $C _ 2$ $\ldots$ $C _ M$
输出
打印一行，包含第$j$件商品的销售额，其中$j=1,2,\ldots,M$，各值之间用空格分隔。
样例输入1
5 4 100 200 300 400 500 120 370 470 80
样例输出1
1280 2350 2850 1140
例如，他可以将第$1$件商品的价格设定为$320$；那么第$2$位、第$3$位、第$4$位和第$5$位顾客将购买一件。 第$1$件商品的销售额将为$1280$。 由于他不能使第$1$件商品的销售额超过$1280$，因此要打印的第一个值为$1280$。
样例输入2
4 4 0 2 10 2 13 13 0 4
样例输出2
52 52 10 18
两位顾客的购买动力可能相同。 同样，两件商品的价值也可能相同。
样例输入3
12 15 16 592 222 983 729 338 747 61 451 815 838 281 406 319 305 519 317 590 507 946 365 5 673 478 340 176 2
样例输出3
6280 5466 5382 7410 5454 8120 7290 11680 5870 3670 8950 7000 5620 4608 3655
样例输入4
5 5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
样例输出4
10000000000 10000000000 10000000000 10000000000 10000000000
请注意，销售额可能不适应$32$位整数类型。