Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-最大开支
题目 3177:

蓝桥杯2023年第十四届省赛真题-最大开支

时间限制: 3s 内存限制: 576MB 提交: 269 解决: 72

题目描述

小蓝所在学校周边新开业了一家游乐园,小蓝作为班长,打算组织大家去游乐园玩。已知一共有 N 个人参加这次活动,游乐园有 M 个娱乐项目,每个项目都需要买门票后才可进去游玩。门票的价格并不是固定的,团购的人越多单价越便宜,当团购的人数大于某个阈值时,这些团购的人便可以免费进入项目进行游玩。这 M 个娱乐项目是独立的,所以只有选择了同一个项目的人才可
以参与这个项目的团购。第 i 个项目的门票价格 Hi 与团购的人数 X 的关系可以看作是一个函数:
Hi(X) = max (Ki × X + Bi , 0)
max 表示取二者之中的最大值。当 Hi = 0 时说明团购人数达到了此项目的免单阈值。
这 N 个人可以根据自己的喜好选择 M 个娱乐项目中的一种,或者有些人对这些娱乐项目都没有兴趣,也可以选择不去任何一个项目。每个人最多只会选择一个娱乐项目,如果多个人选择了同一个娱乐项目,那么他们都将享受对应的团购价格。小蓝想知道他至少需要准备多少钱,使得无论大家如何选择,他都有能力支付得起所有 N 个人购买娱乐项目的门票钱。

输入格式

第一行两个整数 N、M,分别表示参加活动的人数和娱乐项目的个数。
接下来 M 行,每行两个整数,其中第 i 行为 Ki、Bi,表示第 i 个游乐地点的门票函数中的参数。

输出格式

一个整数,表示小蓝至少需要准备多少钱,使得大家无论如何选择项目,自己都支付得起。

样例输入

4 2
-4 10
-2 7

样例输出

12

提示

样例中有 4 个人,2 个娱乐项目,我们用一个二元组 (a, b) 表示 a 个人选择了第一个娱乐项目,b 个人选择了第二个娱乐项目,那么就有 4 − a − b 个人没有选择任何项目,方案 (a, b) 对应的门票花费为 max(−4 × a + 10, 0) × a +max(−2 × b + 7, 0) × b,所有的可能如下所示:

a b 花费
0 0 0
0 1 5
0 2 6
0 3 3
0 4 0
1 0 6
1 1 11
1 2 12
1 3 9
2 0 4
2 1 9
2 2 10
3 0 0
3 1 5
4 0 0

其中当 a = 1, b = 2 时花费最大,为 12。此时 1 个人去第一个项目,所以第一个项目的单价为 10 − 4 = 6,在这个项目上的花费为 6 × 1 = 6;2 个人去第二个项目,所以第二个项目得单价为 7 − 2 × 2 = 3,在这个项目上的花费为2 × 3 = 6;还有 1 个人没去任何项目,不用统计;总花费为 12,这是花费最大的一种方案,所以答案为 12。
对于 30% 的评测用例,1 ≤ N, M ≤ 10。
对于 50% 的评测用例,1 ≤ N, M ≤ 1000。
对于 100% 的评测用例,1 ≤ N, M, Bi ≤ 105,−105 ≤ Ki < 0。


标签