#2928. stong9070奇遇记之商业竞争

stong9070奇遇记之商业竞争

说明

本题使用了Special Judge来Y(^_^)Y

Sepcial Judge Module By stong9070

背景

stong9070者,三国M国之谋士也,忽生异志,舍策士之业,欲助山间贫童习书,然乏资财,遂欲为商贾以致富。

题目描述

NN个城镇位于一条线上,编号为1到NN,商人stong9070从1号城镇前往N号城镇旅游,同时想买卖苹果赚取旅游费用和资助山区儿童的资金。

stong9070将在没有苹果的情况下从1号城镇开始旅行。旅行过程中可以执行的操作如下:

  • move:当在城镇i(iN)i(i<N)时,移动到城镇ii+1
  • merchandise: 在当前城镇购买或出售任意数量的苹果。这里,假设一个苹果总是可以在城镇i(1iN)i(1≤i≤N)AiA_i的价格买卖,其中AiA_i是不同的整数。此外,假设有无限的金钱供应。

出于某种原因,在旅行期间推销苹果数量是有限制的:在整个旅行期间购买的苹果数量和出售的苹果数量之和最多只能是TT(注意,一个苹果买与卖均算一次)

在旅行期间,stong9070将展示他的商业天赋,使旅行的利润最大化。在这里,旅行的利润是卖苹果赚的钱(卖苹果获得的钱减去买苹果花的钱)。请注意,stong9070对旅行结束时拥有的苹果数量不感兴趣。

stong9070的商业竞争对手冷亦萧想通过操纵苹果的市场价格来制造麻烦。在stong9070旅行开始之前,冷亦萧可以多次将任意城镇iiAiA_i变为另一个任意的非负整数AiA_{i'}。执行此操作的成本为 |AiAiA_i−A_{i′}|。执行此操作后,不同的城镇可能具有相等的AiA_i值。

冷亦萧的目标是将stong9070的预期利润至少减少1元。找到实现这一目标的最低总成本。你可以假设stong9070的预期利润最初至少是1元。

输入格式

第一行两个整数N,TN,T

第二行NN个整数AiA_iAiA_i各不相同

输出格式

输出冷亦萧最低总成本,使stong9070的预期利润至少减少1元。

样例

3 2
100 50 200
1

样例解释

在初始状态下,stong9070可以实现的最大利润150元,如下:

  • 1、从城镇1旅游到城镇2
  • 2、在城镇2花50元买一个苹果
  • 3、从城镇2旅游到城镇3
  • 4、在城镇3以200元卖一个苹果

例如,冷亦萧在城镇2把苹果的价格从50元改变至51元,stong9070将无法实现的利润150元。执行此操作的成本为1,因此答案是1。

冷亦萧还有其他方法可以降低stong9070的预期利润,比如在城镇3把苹果的价格从200元改变至199元。

5 8
50 30 40 10 20
2
10 100
7 10 4 5 9 3 6 8 2 1
2

数据范围

  • 1N1051\leq N \leq 10^5
  • 1Ai109(1iN)1 \leq A _i \leq 10^9(1 \leq i \leq N)
  • AiA _i 各不相同
  • 2T1092 \leq T \leq 10^9
  • 在最初的状态下,stong9070的预期利润至少为1元