Rank svakog elementa

Pitanja i problemi
1

Pitanje ili opis problema

Nemam ideju kako da odredim rank svakog elementa. Svatio sam da bi trebalo imena uneti kao stringove a poene kao niz brojeva, znao bih naći najveći element i najmanji, ali ne znam kako odrediti rank bodova.

Link ka zadatku ili odgovarajućoj stranici

https://petlja.org/biblioteka/r/problemi/zbirka-napredni-nivo/rang_svakog_elementa

2

Prvo napravis jedan niz koji ce da cuva parove elemenata i parovi ce biti vrednost koji je neko osvojio i njegova pozicija u nizu. Nakon toga cemo ga sortirati u opadajuci niz gledajuci vrednosti poena. Zatim cemo uzeti drugu vrednost para u nizu i postaviti resenje od te druge pozicije jednako poziciji tog clana u nizu. Evo koda za lakse razumevanje :slight_smile: :

#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> a,pair<int,int> b){
return a.first > b.first;
}
int main()
{
int n;
cin>>n;
int x[n];
vector<pair<int,int> > v;
string a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
cin>>x[i];
v.push_back(make_pair(x[i],i));
}
sort(v.begin(),v.end(),cmp);
int ans[n];
for(int i=0;i<n;i++)
{
ans[v[i].second]=i+1;
}
for(int i=0;i<n;i++)
cout<<a[i]<<" "<<ans[i]<<endl;
}

1 Like
3

Možeš i da prepišeš sve brojeve u novi niz, sortiraš taj niz i onda sa lower_bound dobiješ rank (od pozadi), lako je onda dobiti i rank koji se traži

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<pair<string,int>> items;
    vector<int> s; 
    for(int i = 0; i < n; i++) {
        string name;
        int score;
        cin >> name >> score;
        items.push_back(make_pair(name,score));
        s.push_back(score);
    }
    sort(s.begin(), s.end());
    for(auto item: items) {
        int r = lower_bound(s.begin(), s.end(), item.second) - s.begin();
        cout << item.first << " " << n - r << endl;
    }
    return 0;
}
1 Like