P6886: 任务Čokolade

---

【题目描述】

【题目描述】
小拉娜和小弗兰正在参观巧克力工厂。他们看到了巧克力做好了，尝了很多巧克力，现在又想买一些巧克力。
在商店里，有n种不同的巧克力，第i种巧克力有价格ci。 
拉娜和小弗兰想买巧克力。
小弗兰找到了一个分摊成本的方法:
•如果巧克力比k 库纳便宜，拉娜会付钱。
•否则，拉娜 将支付k库纳，而弗兰将支付剩余的，即ci - k库纳。
我们设l为拉娜需要支付的金额，f为弗兰需要支付的金额。拉娜,不满意在与弗兰的交易中，他想要激怒弗兰并选择巧克力，因此表达式l−f的值为越小越好。由于弗兰犹豫不决，不知道自己想买多少，Lana想买知道q个不同的数ki和mi时表达式l - f的最小值．
请帮助她选择巧克力，并确定每个q的表达式l - f的最小值。
【输入格式】
第一行包含两个整数n和q(1≤n, q≤10^5))，表赤巧克力的数量，以及
查询。
第二行包含n个整数c1, c2，…， cq(1≤ci≤10^9)，表示巧克力的价格。
下面的q行包含整数ki和mi(1≤ki≤10^9)，1≤mi≤n)， Fran界，和
他们要买多少巧克力。
【输出格式】
打印q行。在第i行打印Lana的第i个查询的答案。
【输入样例一】
5 2
1 9 22 10 19
18 4
5 2
【输出样例一】
34
-21
【输入样例二】
7 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 5
【输出样例二】
4
16
7
1
【输入样例三】
3 3
5 6 7
10 1
5 3
3 3
【输出样例三】
5
12
0
【样例一说明】
在第一个查询中，Lana可以选择价格为1、9、22和10的巧克力。拉娜会付38库纳，弗兰4 kuna。答案是38−4 = 34。
在第二个查询中，Lana将选择价格为22和19的巧克力。她会付10库纳，弗兰会付31库纳。答案是10−31 =−21。
【数据约束】

子任务	点	约束条件
1	15	n, q≤1000,ci， ki≤10^6
2	20	k1 =…= kn
3	35	没有其他限制

 
 

题目类型~

COCI-2022/2023-1 

咻咻~

提交答案 状态 返回