Morjani və binalar#12330

Morjani və binalar (Həll təhlili)

Problem Müəllifi:	Hadi Takla
Hazırlayan:	Hadi Takla
Redaktə edən:	Hadi Takla

Həll ilk öncə, $mx$ -i $max (h_{1}, h_{2}, ..., h_{k - 1})$ \max (h_1 , h_2 , ... , h_{k-1}) olaraq təyin edək.

Biz $k_{t h}$ k_{th} binanın görünməsini istəyirik, buna görə aşağıdakı şərt yerinə yetirilməlidir.

$h_{i} < h_{k}$ h_i < h_k bütün $i$ üçün ( $1 \leq i < k$ 1 \le i < k).

Başqa sözlə.

h_{k} > mx

h_k > \text{mx}

Əgər şərt artıq yerinə yetirilmişdirsə, heç bir əməliyyat etməyə ehtiyac yoxdur, əks halda, $h_{k}$ h_k-dan hündür olan bir neçə hündürlük ola biləcəyindən, $k_{t h}$ k_{th} binanın hündürlüyünü artırmaq həmişə optimaldır ki, o, $mx$ -dan hündür olsun.

Beləliklə, cavab $max (0, mx - h_{k} + 1)$ \max (0 , \text{mx} - h_k + 1)-dir.

Zaman mürəkkəbliyi: $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;
    }
}