c++ - 为什么我需要在 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 和 priority_queue 期望提供的类型是可排序的(有 operator< )。

因为您的 bounded 都没有也不是你的total这样做，在这两种情况下你都必须提供你自己的函数。您所询问的格式差异只是界面的一个产物。

在这两种情况下，更简单或更优雅的解决方案是定义 comparison operators根据您的类型。

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

您应该填写其余的比较运算符以获得良好的形式(或者如果您使用的是 c++20 或更高版本，则只需填写 compare_three_way 、 operator<=> )。