#include <iostream> #include <set> #include <vector> #include <algorithm> using namespace std; class Delivery { public: int id = 0; int w = 0; int t = 0; set<Delivery*> breakingDeliveries; friend std::ostream& operator<<(std::ostream& os, const Delivery& obj); bool operator< (const Delivery& msgObj) const { return this->id < msgObj.id; } bool lrConflictWithDt(Delivery dt) { return dt.t + w == dt.w + t; } void remove() { for (auto& b : breakingDeliveries) { b->breakingDeliveries.erase(this); } breakingDeliveries.clear(); } }; std::ostream& operator<<(std::ostream& os, const Delivery& obj) { os << "City(" << obj.id << "," << obj.w << "," << obj.t << endl; for (auto& b : obj.breakingDeliveries) { os << b->id << ","; } return os << endl << ")" << endl; } int main(int argc, char** argv) { int n; cin >> n; vector<Delivery*> all; vector<Delivery*> leftToRight; vector<Delivery*> downToUp; long long int wholeRouteSum = 0; for (int i = 0; i < n; i++) { int r, w, t; cin >> r >> w >> t; Delivery* newDelivery = new Delivery(); newDelivery->id = i; newDelivery->w = w; newDelivery->t = t; if (r == 1) { downToUp.push_back(newDelivery); } else { leftToRight.push_back(newDelivery); } all.push_back(newDelivery); } for (auto& lr : leftToRight) { for (auto& dt : downToUp) { if (lr->lrConflictWithDt(*dt)) { if (dt->breakingDeliveries.size() == 0) { lr->breakingDeliveries.insert(dt); dt->breakingDeliveries.insert(lr); } else { Delivery* alsoBreaksWithLr = (*next(dt->breakingDeliveries.begin(), 0)); for (auto& breakingDt : alsoBreaksWithLr->breakingDeliveries) { lr->breakingDeliveries.insert(breakingDt); breakingDt->breakingDeliveries.insert(lr); } break; } } } } int removed = 0; while (true) { vector<Delivery*>::iterator withMax = max_element(all.begin(), all.end(), [](Delivery* i1, Delivery* i2) { return i1->breakingDeliveries.size() < i2->breakingDeliveries.size(); }); if (withMax == all.end()) { break; } if ((*withMax)->breakingDeliveries.size() == 0){ break; } (*withMax)->remove(); all.erase(withMax); removed++; } cout << removed << endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <iostream> #include <set> #include <vector> #include <algorithm> using namespace std; class Delivery { public: int id = 0; int w = 0; int t = 0; set<Delivery*> breakingDeliveries; friend std::ostream& operator<<(std::ostream& os, const Delivery& obj); bool operator< (const Delivery& msgObj) const { return this->id < msgObj.id; } bool lrConflictWithDt(Delivery dt) { return dt.t + w == dt.w + t; } void remove() { for (auto& b : breakingDeliveries) { b->breakingDeliveries.erase(this); } breakingDeliveries.clear(); } }; std::ostream& operator<<(std::ostream& os, const Delivery& obj) { os << "City(" << obj.id << "," << obj.w << "," << obj.t << endl; for (auto& b : obj.breakingDeliveries) { os << b->id << ","; } return os << endl << ")" << endl; } int main(int argc, char** argv) { int n; cin >> n; vector<Delivery*> all; vector<Delivery*> leftToRight; vector<Delivery*> downToUp; long long int wholeRouteSum = 0; for (int i = 0; i < n; i++) { int r, w, t; cin >> r >> w >> t; Delivery* newDelivery = new Delivery(); newDelivery->id = i; newDelivery->w = w; newDelivery->t = t; if (r == 1) { downToUp.push_back(newDelivery); } else { leftToRight.push_back(newDelivery); } all.push_back(newDelivery); } for (auto& lr : leftToRight) { for (auto& dt : downToUp) { if (lr->lrConflictWithDt(*dt)) { if (dt->breakingDeliveries.size() == 0) { lr->breakingDeliveries.insert(dt); dt->breakingDeliveries.insert(lr); } else { Delivery* alsoBreaksWithLr = (*next(dt->breakingDeliveries.begin(), 0)); for (auto& breakingDt : alsoBreaksWithLr->breakingDeliveries) { lr->breakingDeliveries.insert(breakingDt); breakingDt->breakingDeliveries.insert(lr); } break; } } } } int removed = 0; while (true) { vector<Delivery*>::iterator withMax = max_element(all.begin(), all.end(), [](Delivery* i1, Delivery* i2) { return i1->breakingDeliveries.size() < i2->breakingDeliveries.size(); }); if (withMax == all.end()) { break; } if ((*withMax)->breakingDeliveries.size() == 0){ break; } (*withMax)->remove(); all.erase(withMax); removed++; } cout << removed << endl; return 0; } |