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
– Input
First line contains integer T, denoting the number of testcases.
For each testcases
First line contains integer N, denoting number of employees,
Second line contains N space separated integers, denoting the rank of each employee.
- Output
For each testcase print the number of minimum gifts required on new line.
Answers
Answer:
include <iostream>
#include <stack>
using namespace std;
const int MAXN = 100000;
int g[MAXN][3];
int indeg[MAXN];
int val[MAXN];
int c[MAXN];
int n;
int main() {
int t ;
scanf("%d",&t);
while(t--){
cin >> n;
for (int i = 0; i < n; i++) cin >> val[i];
if (n == 1) {
cout << 1 << endl;
return 0;
}
for (int i = 0; i < n - 1; i++) {
if (val[i] < val[i + 1]) {
g[i][++g[i][0]] = i + 1;
indeg[i + 1]++;
} else if(val[i] > val[i + 1]) {
g[i + 1][++g[i + 1][0]] = i;
indeg[i]++;
}
}
stack<int> sta;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) {
c[i] = 1;
sta.push(i);
}
}
while (!sta.empty()) {
int r = sta.top();
sta.pop();
for (int j = 1; j <= g[r][0]; j++) {
c[g[r][j]] = max(c[g[r][j]], c[r] + 1);
indeg[g[r][j]]--;
if (indeg[g[r][j]] == 0) sta.push(g[r][j]);
}
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += c[i];
}
cout << ans << endl;
}}
Answer:
#include <iostream>
#include <stack>
using namespace std;
const int MAXN = 100000;
int g[MAXN][3];
int indeg[MAXN];
int val[MAXN];
int c[MAXN];
int n;
int main() {
int t ;
scanf("%d",&t);
while(t--){
cin >> n;
for (int i = 0; i < n; i++) cin >> val[i];
if (n == 1) {
cout << 1 << endl;
return 0;
}
for (int i = 0; i < n - 1; i++) {
if (val[i] < val[i + 1]) {
g[i][++g[i][0]] = i + 1;
indeg[i + 1]++;
} else if(val[i] > val[i + 1]) {
g[i + 1][++g[i + 1][0]] = i;
indeg[i]++;
}
}
stack<int> sta;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) {
c[i] = 1;
sta.push(i);
}
}
while (!sta.empty()) {
int r = sta.top();
sta.pop();
for (int j = 1; j <= g[r][0]; j++) {
c[g[r][j]] = max(c[g[r][j]], c[r] + 1);
indeg[g[r][j]]--;
if (indeg[g[r][j]] == 0) sta.push(g[r][j]);
}
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += c[i];
}
cout << ans << endl;
}}