Sorting array and saving the old index in C++

Question

I am doing online challenge which has to do the following.

There is a contest going in a village. So in the first line input two numbers N (which is how many people will join the contest) and K (how many of them can go to stage 2).

After that, we input N times the votes for each candidate in both stages.

Example input:

As you can see, we input N=5, K=3, which means 5 candidates, so 5 additional lines and 3 of them which go to stage 2.

After we sort the array the candidates with most votes are the ones with 6, 8 and 9. So they're going to stage 2. The winner is the one who has most votes in the stage 2 of them. In this case, 6 has 5 votes which is the most (8 has 4 and 9 has 2) and therefore we output the index of the 6 which is 5.

What I got so far:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[50],nizabackup[50],n,k,niza2[50],saveindex[50],indexp=0;
    cin >> n >> k;
    for(int i=0;i<n;i++)
    {
        cin >> arr[i] >> niza2[i];
        nizabackup[i] = arr[i];
    }
    sort(arr,arr+n);
    for(int j=n;j>=k;j--)
    {
        for(int k=0;k<n;k++)
        {
            if(arr[j]==nizabackup[k])
            {
                saveindex[0]=k;
                indexp++;
            }
        }
    }
    sort(saveindex,saveindex+indexp);
    cout << saveindex[indexp];
    return 0;
}

I need a hint what to do and also additional question -- why my debugger doesn't read the second for loop?

It seems you probably want `j >= k` in your second `for` loop, since `n` is greater than `k`. — Joseph Mansfield, Mar 28 '13 at 12:14

Useless · Accepted Answer · 2013-03-28T14:18:17.337

3

OK, alternative implementation. There's more set-up, but read main first and see how much simpler the actual logic is.

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

struct Contestant {
    int index;
    int firstVote;
    int secondVote;
    Contestant(int i, int v1, int v2) : index(i), firstVote(v1), secondVote(v2)
    {}
};
// return true if l should come before r in sorted result
bool byFirstVote(Contestant const &l, Contestant const &r) {
    return l.firstVote > r.firstVote; // sort by first vote
}
bool bySecondVote(Contestant const &l, Contestant const &r) {
    return l.secondVote > r.secondVote; // sort by second vote
}

int main()
{
    int n, k;
    std::cin >> n >> k;
    // populate a single vector of {index, firstVote, secondVote}
    std::vector<Contestant> contestants;
    for(int i=0; i<n; i++) {
        int v1, v2;
        std::cin >> v1 >> v2;
        contestants.push_back(Contestant(i+1, v1, v2));
    }
    // sort all by firstVote, then sort first k by secondVote
    std::sort(contestants.begin(), contestants.end(), byFirstVote);
    std::sort(contestants.begin(), contestants.begin()+k, bySecondVote);
    std::cout << contestants.front().index << std::endl;
}

I'm storing the index (starting from 1, not zero, as per your example), and both votes, all together in a single structure.

Then, I just change which field I sort on.

edited Mar 28 '13 at 14:18

answered Mar 28 '13 at 12:56

Useless

64,155
6
88
132

Ah. This made me realise the issue with my answer. +1 – SlxS Mar 28 '13 at 13:00
Wow, pretty good implementation to be honest. I think vectors are kinda more useful than arrays somehow. Anyway, I've got a few questions to ask. What does the following code do `Contestant(int i, int v1, int v2) : index(i), firstVote(v1), secondVote(v2)` ? And why do we have additional `{}` below it? What exactly are we checking in the bool functions? Thanks in advance. – John Smith Mar 28 '13 at 13:08
@JohnSmith `Contestant(int i, int v1, int v2) : index(i), firstVote(v1), secondVote(v2)` is an initialization list, it is ~Similar~ to doing this `Contestant(int i, int v1, int v2) {index=i;firstVote=v1;secondVote=v2;}`, the empty {} on the initialization list is the empty body of the function. An initialization list is dealt with before the body of the function runs. – Daboyzuk Mar 28 '13 at 13:19
I understand! And the bool function I don't understand where does l or r come from and where do we use it? – John Smith Mar 28 '13 at 13:27
So the (optional) 3rd argument to [`std::sort`](http://en.cppreference.com/w/cpp/algorithm/sort) is a comparator taking two arguments (const references to whatever types you're sorting - here we are sorting `Contestant`s, so they are `Contestant const &`) and returning a bool. The bool should be `true` if the left comparand should come _before_ the right in the sorted set, and `false` otherwise. The `std::sort` without the third argument just uses `operator<`, so by default sorts in ascending order. – Useless Mar 28 '13 at 14:12
... and after writing that comment, I realized my comparisons were in the wrong direction, and your example _happened_ to work anyway. Fixed now! – Useless Mar 28 '13 at 14:26

Sorting array and saving the old index in C++

1 Answers1

Linked