#include <iostream> #include <vector> #include <tuple> #include <algorithm> using namespace std; class samochod { public: int t, x, L; samochod(int t0, int x0){t=t0; x=x0; L=t-x;} friend bool operator< (const samochod a, const samochod b) { return tie(a.L, a.x, a.t) < tie(b.L, b.x, b.t); } }; int main() { std::ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; vector<samochod> poziome, pionowe; poziome.reserve(n); pionowe.reserve(n); for (int ii=0; ii<n; ii++) { int kier, x, t; cin>>kier>>x>>t; if (kier==1) pionowe.push_back(samochod(t,x)); else poziome.push_back(samochod(t,x)); } sort(poziome.begin(), poziome.end()); sort(pionowe.begin(), pionowe.end()); int Wyrzucic=0; auto itA = poziome.begin(), itB=pionowe.begin(); while (itA!=poziome.end() && itB != pionowe.end()) { int licznikA=0, licznikB=0; int La = itA->L; // zlicz wszystkie poziome z ta sama liczba L: while(itA!=poziome.end() && itA->L ==La) { licznikA++; ++itA; } // pomin pionowe z za mala liczba L: while(itB != pionowe.end() && itB->L <La) ++itB; // zlicz wszystkie pionowe z ta sama liczba L=La: while(itB != pionowe.end() && itB->L ==La) { licznikB++; ++itB; } // znaleziony zestaw kolizji - wyrzuc wszystkie dostawy z jednego kierunku (te ktorych jest mniej) Wyrzucic += min(licznikA, licznikB); } cout<<Wyrzucic<<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 | #include <iostream> #include <vector> #include <tuple> #include <algorithm> using namespace std; class samochod { public: int t, x, L; samochod(int t0, int x0){t=t0; x=x0; L=t-x;} friend bool operator< (const samochod a, const samochod b) { return tie(a.L, a.x, a.t) < tie(b.L, b.x, b.t); } }; int main() { std::ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; vector<samochod> poziome, pionowe; poziome.reserve(n); pionowe.reserve(n); for (int ii=0; ii<n; ii++) { int kier, x, t; cin>>kier>>x>>t; if (kier==1) pionowe.push_back(samochod(t,x)); else poziome.push_back(samochod(t,x)); } sort(poziome.begin(), poziome.end()); sort(pionowe.begin(), pionowe.end()); int Wyrzucic=0; auto itA = poziome.begin(), itB=pionowe.begin(); while (itA!=poziome.end() && itB != pionowe.end()) { int licznikA=0, licznikB=0; int La = itA->L; // zlicz wszystkie poziome z ta sama liczba L: while(itA!=poziome.end() && itA->L ==La) { licznikA++; ++itA; } // pomin pionowe z za mala liczba L: while(itB != pionowe.end() && itB->L <La) ++itB; // zlicz wszystkie pionowe z ta sama liczba L=La: while(itB != pionowe.end() && itB->L ==La) { licznikB++; ++itB; } // znaleziony zestaw kolizji - wyrzuc wszystkie dostawy z jednego kierunku (te ktorych jest mniej) Wyrzucic += min(licznikA, licznikB); } cout<<Wyrzucic<<endl; return 0; } |