A Company has decided to give some gifts to all of its employees. For that, company has given some rank to each employee. Based on that rank, company has made certain rules to distribute the gifts. The rules for distributing the gifts are: Each employee must receive at least one gift. Employees having higher ranking get a greater number of gifts than their neighbours. What is the minimum number of gifts required by company? Constraints 1 < T < 10 1 < N < 100000 1 < Rank < 10^9
Answers
Answer:
please mark me as brainliest I will
Explanation:
please mark me as brainliest I will
Program in C++:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cout<<"Enter total number of employees : ";
cin>>N;
int Rank[N];
if(N < 1 || N > 100000)
{
cout<<"Invalid Input";
return 0;
}
cout<<"Enter ranks of each employees : "<<endl;
for(int i = 0; i < N; i++)
{
cin>>Rank[i];
if(Rank[i] < 1 || Rank[i] > (int)pow(10, 9))
{
cout<<"Invalid Input";
return 0;
}
}
int gifts[N];
fill(gifts, gifts + N, 1);
for(int i = 0; i < N-1; i++)
{
if(Rank[i] > Rank[i+1] && gifts[i] <= gifts[i+1])
{
gifts[i] = gifts[i+1] + 1;
for(int j = i; j > 0; j--)
{
if(Rank[j-1] > Rank[j] && gifts[j-1] <= gifts[j])
{
gifts[j-1] = gifts[j] + 1;
}
else
{
break;
}
}
}
else if(Rank[i] < Rank[i+1] && gifts[i+1] <= gifts[i])
{
gifts[i+1] = gifts[i] + 1;
}
}
int sum = 0;
for(int i = 0; i < N; i++)
{
sum = sum + gifts[i];
}
cout<<"Number of minimum gifts required : "<<sum;
return 0;
}
Output 1:
Enter total number of employees : 5
Enter ranks of each employees :
1
2
1
5
2
Number of minimum gifts required : 7
Output 2:
Enter total number of employees : 2
Enter ranks of each employees :
1
2
Number of minimum gifts required : 3