100473: [AtCoder]ABC047 D - An Invisible Hand

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $400$ points

Problem Statement

There are $N$ towns located in a line, conveniently numbered $1$ through $N$. Takahashi the merchant is going on a travel from town $1$ to town $N$, buying and selling apples.

Takahashi will begin the travel at town $1$, with no apple in his possession. The actions that can be performed during the travel are as follows:

  • Move: When at town $i$ ($i < N$), move to town $i + 1$.
  • Merchandise: Buy or sell an arbitrary number of apples at the current town. Here, it is assumed that one apple can always be bought and sold for $A_i$ yen (the currency of Japan) at town $i$ ($1 ≦ i ≦ N$), where $A_i$ are distinct integers. Also, you can assume that he has an infinite supply of money.

For some reason, there is a constraint on merchandising apple during the travel: the sum of the number of apples bought and the number of apples sold during the whole travel, must be at most $T$. (Note that a single apple can be counted in both.)

During the travel, Takahashi will perform actions so that the profit of the travel is maximized. Here, the profit of the travel is the amount of money that is gained by selling apples, minus the amount of money that is spent on buying apples. Note that we are not interested in apples in his possession at the end of the travel.

Aoki, a business rival of Takahashi, wants to trouble Takahashi by manipulating the market price of apples. Prior to the beginning of Takahashi's travel, Aoki can change $A_i$ into another arbitrary non-negative integer $A_i'$ for any town $i$, any number of times. The cost of performing this operation is $|A_i - A_i'|$. After performing this operation, different towns may have equal values of $A_i$.

Aoki's objective is to decrease Takahashi's expected profit by at least $1$ yen. Find the minimum total cost to achieve it. You may assume that Takahashi's expected profit is initially at least $1$ yen.

Constraints

  • $1 ≦ N ≦ 10^5$
  • $1 ≦ A_i ≦ 10^9$ ($1 ≦ i ≦ N$)
  • $A_i$ are distinct.
  • $2 ≦ T ≦ 10^9$
  • In the initial state, Takahashi's expected profit is at least $1$ yen.

Input

The input is given from Standard Input in the following format:

$N$ $T$
$A_1$ $A_2$ $...$ $A_N$

Output

Print the minimum total cost to decrease Takahashi's expected profit by at least $1$ yen.

Sample Input 1

3 2
100 50 200

Sample Output 1

1

In the initial state, Takahashi can achieve the maximum profit of $150$ yen as follows:

  1. Move from town $1$ to town $2$.
  2. Buy one apple for $50$ yen at town $2$.
  3. Move from town $2$ to town $3$.
  4. Sell one apple for $200$ yen at town $3$.

If, for example, Aoki changes the price of an apple at town $2$ from $50$ yen to $51$ yen, Takahashi will not be able to achieve the profit of $150$ yen. The cost of performing this operation is $1$, thus the answer is $1$.

There are other ways to decrease Takahashi's expected profit, such as changing the price of an apple at town $3$ from $200$ yen to $199$ yen.

Sample Input 2

5 8
50 30 40 10 20

Sample Output 2

2

Sample Input 3

10 100
7 10 4 5 9 3 6 8 2 1

Sample Output 3

2

Input

题意翻译

# 高桥君和不可见之手 ## 问题描述 有 $N$ 个小镇排在一条直线上。旅行商人高桥君从小镇 $1$ 出发，一边买卖苹果一边朝小镇 $N$ 前行。 开始时高桥君处在小镇 $1$ ，身上一个苹果也没有。高桥君不断进行以下行动。 - 移动：从小镇 $i(i < N)$ 开始，移动到小镇 $i+1$ 。 - 买卖苹果：买进或卖出任意个苹果。在小镇 $i(1 \leq i \leq N)$ 买进或卖出苹果单价都为 $A_i$ 円。 $A_i$ 为相异的整数。 在每个小镇进行交易的苹果数量没有限制，但是旅行中所买进和卖出的苹果总数(买进苹果数加上卖出苹果数)必须在 $T$ 以内。高桥君会使自己在旅程中所获利益(卖苹果所得钱数减去买苹果所花钱数)最大。 在高桥君进行旅行之前，青木君可以对于任意 $i$ ，使 $A_i$ 变为非负整数 $A_i'$ 。这个操作的代价为 $|A_i-A_i'|$ 。操作后即使出现相异小镇苹果单价相同的情况也没关系。 青木君的目的是：花费尽量少的代价，使高桥君所得的最大利益至少下降 $1$ 円。请求出最小代价。 数据保证初始状态下高桥君至少能获得 $1$ 円的利益。 ## 数据范围 - $1 \leq N \leq 10^5$ - $1 \leq A_i \leq 10^9$ - $A_i$ 相异 - $2 \leq T \leq 10^9$ - 保证初始状态下高桥君至少能获得 $1$ 円的利益。 ## 输入 输入按以下标准： $$ N \space T $$ $$ A_1 \space A_2 \space \dots \space A_N $$ ## 输出 输出使高桥君最大收益至少下降 $1$ 円的最小代价和。 ## 样例1解释 在初始状态下，高桥君能够进行以下的行动来获得最大收益( $150$ 円)： 1. 从小镇 $1$ 移动到小镇 $2$ 。 1. 在小镇 $2$ 处花 $50$ 円买一个苹果。 1. 从小镇 $2$ 移动到小镇 $3$ 。 1. 在小镇 $3$ 处卖掉一个苹果获得 $200$ 円。 举例来说，如果青木君把小镇 $2$ 的苹果单价从 $50$ 円上调至 $51$ 円，高桥君就无法获得 $150$ 円的收益。也就是说，此操作能够使高桥君的最大收益至少下降 $1$ 円，所以答案为 $1$ 。 另外，将小镇 $3$ 的苹果单价从 $200$ 円降至 $199$ 円也能够达到目的。

Source/Category

加入题单

上一题 下一题 算法标签：