Problem Link:
Author: the_death
Tester:the_death
Editorialist:the_death
Difficulty:
Easy
Prerequisites:
Sorting
Problem:
There are N people are standing in a row, each with a score.
Chef wants to give medals to all of them . For each person A_i (1 \leq i \leq N) with a score P_i, Chef gets one point for each person ahead of A_i with a score strictly greater than P_i. Once a person is given the medal he will not be accounted for points calculation anymore. Chef cannot change the order in which people stand in the row
Given that Chef can give medals in any order. What is the maximum score Chef can attain?
Explanation:
Brute force solution is to find for each number the number of numbers ahead of it with score more using two loops. this would take O(n^2).
An efficient solution would be to sort it first and for every element in the unsorted array (u maintain two arrays one sorted and one not) u simply calculate the number of numbers ahead of it and afterwards u delete it.
Time Complexity:
O(NlogN)
Solution:
Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> v,a;
int n;
cin>>n;
int b;
for(int i=0;i<n;i++)
{
cin>>b;
a.push_back(b);
v.push_back(b);
}
long int sum = 0;
sort(v.begin(),v.end());
vector<int> ::iterator itr;
for(int i=0;i<a.size();i++)
{
itr = upper_bound(v.begin(),v.end(),a[i]);
sum+=v.end() - itr;
v.erase(itr - 1);
}
cout<<sum<<endl;
}