Question Name:TABLETS

#include <iostream>
 
using namespace std;
 
int main() {
	long int n,i,temp,sum=0;
cin>>n;
long int hs[n],dp[n];
for(i=0;i<n;i++){
    cin>>hs[i];
}
for(i=0;i<n;i++){
    dp[i]=1;
}
for(i=1;i<n;i++){
    if(hs[i]>hs[i-1]){
        dp[i]=dp[i-1]+1;
    }
}
for(i=n-2;i>=0;i--){
    if((hs[i]>hs[i+1])&&dp[i]<=dp[i+1]){
        dp[i]=dp[i+1]+1;
    }
}
for(i=0;i<n;i++){
   sum+=dp[i];
}
cout<<sum;
 
}
  • Problem Description
    Therasa is a Nurse. She wants to give some tablets to the patients in her practice. All the patients sit in a line and each of them has a rating score according to his or her health score. 

    Therasa wants to give at least 1 tablet for each patient. Patients get jealous of their immediate neighbours, so if two patients sit next to each other then the one with the higher rating must get more tablets. Therasa wants to save money, so she wants to minimize the total number of tablets.

    Input
    The first line of the input is an integer N, the number of patients in Therasas practice. Each of the following N lines contains an integer indicates the health score of each patient.

    Output
    Output a single line containing the minimum number of tablets Therasa must give.

    Constraints
    1 <= N <= 100000
  • Test Case 1
    Input (stdin)3 1 2 2
    Expected Output4
  • Test Case 2
    Input (stdin)7 1 2 5 6 10 19 12 20 12 21
    Expected Output22

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro