Why do I need different sorting formats in C++ for sorting arrays and priority queues on this USACO code?

user_10560374 0
Viewed 69

I'm pretty new to C++, and was trying a USACO problem from this past year. This is my code below, which works, but took hours to fiddle around with the formatting. It turns out that I needed

bool sorting(total a, total b) {return a.t < b.t;}

to be able to sort an array of objects (which failed for my priority queue), whereas I needed

struct uppersort {
    bool operator()(bounded a, bounded b) {
    return a.u > b.u;
    }
};

to be able to sort a priority queue (which failed for my array). I'm just wondering why this was true, and if there's a simpler way to do either part. Actually, I'm also just looking for ways to simplify my code in general. Thanks!

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct bounded {
    int cow;
    long l;
    long u;
};

struct total {
    long t;
    long whichcow;
    bool begorend;
};

struct uppersort {
    bool operator()(bounded a, bounded b) {
        return a.u > b.u;
    }
};

bool sorting(total a, total b) {return a.t < b.t;}

int main() {
    ofstream fout ("lifeguards.out");
    ifstream fin ("lifeguards.in");
    long n;
    fin >> n;
    vector<bounded> cows(n);
    for(int i=0; i<n; i++) {
        fin >> cows[i].l >> cows[i].u;
        cows[i].cow = i;
    }
    vector<total> endpoints(2*n);
    for(int i=0; i<n; i++) {
        endpoints[i].t = cows[i].l;
        endpoints[i].whichcow = i;
        endpoints[i].begorend = 0;
        endpoints[n+i].t=cows[i].u;
        endpoints[n+i].whichcow = i;
        endpoints[n+i].begorend = 1;
    }
    sort(endpoints.begin(), endpoints.end(), sorting);
    int containnumber = 0;
    long totaltime = 0;
    vector<long> eachtime(n);
    long prevtime = 0;
    long curtime = 0;
    priority_queue<bounded, vector<bounded>, uppersort> contains;
    for(int i=0; i<2*n; i++) {
        prevtime = curtime;
        curtime = endpoints[i].t;
        if(containnumber==1) {
            eachtime[contains.top().cow] += curtime - prevtime;
        }
        if(containnumber >0) {
            totaltime += curtime - prevtime;
        }
        if(endpoints[i].begorend==0) {
             contains.push(cows[endpoints[i].whichcow]);
             containnumber++;
        } else {
            contains.pop();
            containnumber--;
         }
    }
    long min = -1;
    for(int i=0; i<n; i++) {
        if(min==-1 || eachtime[i]<min) {
            min = eachtime[i];
        }
    }
    fout << totaltime-min << endl;
}
priority-queue c++
1 Answers

Both sort and priority_queue are expecting the provided type to be sort-able (have operator<).

Since neither your bounded nor your total do, you have to provide your own function in both cases. The difference in format you asked about is just an artifact of the interface.

In both cases the simpler or more elegant solution is to define the comparison operators on your types.

struct bounded {
    int cow;
    long l;
    long u;
    bool operator<(bound rhs)const{
        return u<rhs.u;
    }
};

struct total {
    long t;
    long whichcow;
    bool begorend;
    bool operator<(total rhs)const{
        return t<rhs.t;
    }
};

You should fill in the rest of the comparison operators for good form (or just compare_three_way, operator<=>, if you are using c++20 or newer).

user_44999690
Related