## Question

A Company decided to give some gifts its employees. For that, company has given some rank to each employee and made certain rules to distribute the gifts. Find minimum gift required.

# Solution by Ande Dheeraj Reddy.

## Algorithm

Greedy works here ( Think of a supportive proof as as assignment ).
If he did recieve more than one candy, we could lower it to 1 as none of the neighbor have higher rating.
Now lets move to the one which is second least. If the least element is its neighbor, then it receives 2 gifts, else we can get away with assigning it just one gift.

We keep repeating the same process to arrive at optimal solution.

## Solution

``````#include<bits/stdc++.h>
using namespace std;
int size = ratings.size();

// if the vector is empty: return zero
if (size == 0) return gifts;

for (int i = 0; i < size; i++)
{
if (i == size - 1)
{
continue;
}

if (ratings[i + 1] > ratings[i])
{
}
else if (ratings[i + 1] < ratings[i])
{
int startIndex = i;

while (i + 1 < size && ratings[i + 1] < ratings[i])
{
i++;
}

int startgiftStateFromRight = i - startIndex + 1;

// Adjusting for the local maxima point.
{
}

// Let's exclude this local minima point now as this
// will be accounted in the next iteration.
i--;
}
else
{
}
}

// return the miimum gifts required the the given ratings vector
}

//driver code
int main()
{
int t;
cin>>t;
while(t--)
{
long n,l;
cin>>n;
vector<long > rating; // vector of ratings

for(int i=0;i<n;i++)
{ cin>>l;
rating.push_back(l);
}

//print the output, mingifts function return