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.
The complete question can be found here.
Solution by Ande Dheeraj Reddy.
Algorithm
|
Greedy works here ( Think of a supportive proof as as assignment ). |
|
|
Start with the guy with the least rating. Obviously he will receive 1 candy. |
|
|
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 mingifts (vector<int> &ratings) {
int gifts = 0;
int size = ratings.size();
if (size == 0) return gifts;
int giftState = 1;
for (int i = 0; i < size; i++)
{
if (i == size - 1)
{
gifts += giftState;
continue;
}
if (ratings[i + 1] > ratings[i])
{
gifts += giftState;
giftState++;
}
else if (ratings[i + 1] < ratings[i])
{
int startgiftState = giftState;
int startIndex = i;
while (i + 1 < size && ratings[i + 1] < ratings[i])
{
i++;
}
int startgiftStateFromRight = i - startIndex + 1;
gifts += (startgiftStateFromRight + 1)\
* startgiftStateFromRight / 2;
if (startgiftState > startgiftStateFromRight)
{
gifts += startgiftState - startgiftStateFromRight;
}
gifts--;
i--;
giftState = 1;
}
else
{
gifts += giftState;
giftState = 1;
}
}
return gifts;
}
int main()
{
int t;
cin>>t;
while(t--)
{
long n,l;
cin>>n;
vector<long > rating;
for(int i=0;i<n;i++)
{ cin>>l;
rating.push_back(l);
}
cout<<mingifts(rating)<<endl;
}
return 0;
}