Морджані та будівлі#12330

Морджані та будівлі (Розбір)

Автор проблеми:	Хаді Такла
Підготовлено:	Хаді Такла
Редаговано:	Хаді Такла

Рішення Спочатку нехай $mx$ буде $max (h_{1}, h_{2}, ..., h_{k - 1})$ \max (h_1 , h_2 , ... , h_{k-1}).

Нам потрібно, щоб $k_{та}$ k_{та} будівля була видима, тому повинна виконуватись наступна умова.

$h_{i} < h_{k}$ h_i < h_k для всіх $i$ ( $1 \leq i < k$ 1 \le i < k).

Іншими словами.

h_{k} > mx

h_k > \text{mx}

Якщо умова вже виконана, нам не потрібно виконувати жодну операцію, інакше, оскільки ми можемо мати більше ніж одну висоту, що перевищує $h_{k}$ h_k, завжди оптимально збільшити висоту $k_{тої}$ k_{тої} будівлі, поки вона не стане більшою за $mx$ .

Отже, відповідь буде $max (0, mx - h_{k} + 1)$ \max (0 , \text{mx} - h_k + 1).

Часова складність: $O (n)$ .


#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n,k,mx = 0;
        cin>>n>>k;
        int h[n+10];
        for(int i=1;i<=n;i++)
        cin>>h[i];
        for(int i=1;i<k;i++)
        mx = max(mx , h[i]);
        int ans = max(0LL , mx - h[k] + 1);
        cout<<ans<<endl;
    }
}