为什么我需要在C ++中使用不同的排序格式来对此USACO代码上的数组和优先级队列进行排序？

Question

我对C ++还是很陌生，过去一年一直在尝试USACO问题。这是我下面的代码，可以正常工作，但是花了数小时来摆弄格式。原来我需要

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

为了能够对对象数组进行排序（在我的优先级队列中失败，而我需要]

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

能够对优先级队列进行排序（对于我的阵列失败）。我只是想知道为什么这是真的，以及是否有一种更简单的方法来完成这两个部分。实际上，我也只是在寻找简化总体代码的方法。谢谢！

#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;
}

Answer 1

sort和sort都期望提供的类型是可排序的（具有priority_queue）。

由于priority_queue和operator<都没有，因此在两种情况下都必须提供自己的功能。您询问的格式差异仅是界面的人工产物。

在两种情况下，更简单或更优雅的解决方案都是在类型上定义operator<。

bounded

您应该填写其余的比较运算符以确保格式正确（如果使用的是c ++ 20或更高版本，则只需填写total，comparison operators）。