Я новичок в 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(endpoints.begin(), endpoints.end(), [](const total &a, const total &b) { return a.t < b.t; });
последняя петля может быть std::min_element
.
Упрощение было бы разделить функцию :-)
Для рабочего кода более подходящим может быть codereview.stackexchange.com.
И sort
, и priority_queue
ожидают, что предоставленный тип будет иметь возможность сортировки (иметь operator<
).
Поскольку ни ваш bounded
, ни ваш total
этого не делают, вы должны предоставить свою собственную функцию в обоих случаях. Разница в формате, о которой вы спрашивали, - это всего лишь артефакт интерфейса.
В обоих случаях более простым или элегантным решением является определение операторы сравнения для ваших типов.
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;
}
};
Вы должны заполнить остальные операторы сравнения для хорошей формы (или просто compare_three_way
, operator<=>
, если вы используете C++ 20 или новее).
[OT]:
bool sorting(total a, total b) {return a.t < b.t;}
это не сортировка, а сравнение / lessThan / ...