我对 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;
}
最佳答案
两者 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<=>
)。
关于c++ - 为什么我需要在 C++ 中使用不同的排序格式来对这个 USACO 代码上的数组和优先级队列进行排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52999491/