0

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:

5 3
9 2
3 10
5 6
8 4
6 5

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?

1
  • 2
    It seems you probably want j >= k in your second for loop, since n is greater than k. Mar 28, 2013 at 12:14

1 Answer 1

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.

6
  • Ah. This made me realise the issue with my answer. +1
    – SlxS
    Mar 28, 2013 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, 2013 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, 2013 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, 2013 at 13:27
  • So the (optional) 3rd argument to std::sort is a comparator taking two arguments (const references to whatever types you're sorting - here we are sorting Contestants, 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, 2013 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.