Morjani and buildings#12330

Morjani and buildings (Талдоо)

Problem Author:	Hadi Takla
Prepared by:	Hadi Takla
Edited by:	Hadi Takla

Solution at first , let $mx$ be $max (h_{1}, h_{2}, ..., h_{k - 1})$ \max (h_1 , h_2 , ... , h_{k-1}).

we need the $k_{t h}$ k_{th} building to be visible , so the following condition should hold.

$h_{i} < h_{k}$ h_i < h_k for all $i$ ( $1 \leq i < k$ 1 \le i < k).

in other words.

h_{k} > mx

h_k > \text{mx}

if the condition is already fulfilled we don't have to do any operation , otherwise since we can have more than one height greater than $h_{k}$ h_k , it is always optimal to increase the height of the $k_{t h}$ k_{th} building until it is greater than $mx$ .

so the answer is $max (0, mx - h_{k} + 1)$ \max (0 , \text{mx} - h_k + 1)

time complexity : $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;
    }
}