DS_2022_HW5_Sort
unknown
c_cpp
2 years ago
3.8 kB
9
Indexable
#include <bits/stdc++.h> using namespace std; #define INF INT64_MAX #define ll long long #define pll pair<ll,ll> #define DEBUG 0 int n, m; vector<pll> v1; //順向 vector<pll> v2; //逆向 struct Cmp1 { bool operator()(const pll& lhs, const pll& rhs) const{ if(lhs.first == rhs.first){ return lhs.second >= rhs.second; } else{ return lhs.first > rhs.first; } } }; struct Cmp2 { bool operator()(const pll& lhs, const pll& rhs) const{ if(lhs.first == rhs.first){ return lhs.second >= rhs.second; } else{ return lhs.first > rhs.first; } } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; ll s, e; int j=0, k=0; for(int i=0; i<n; i++){ cin >> s >> e; if(s<e){ v1.push_back({s, e}); j++; } else if(s>e){ v2.push_back({s, e}); k++; } } // 按照 Si heapify priority_queue<pll,vector<pll>,Cmp1> p1(v1.begin(), v1.end()); //順向 priority_queue<pll,vector<pll>,Cmp2> p2(v2.begin(), v2.end()); //逆向 ll dis = 0; // ans ll cur = 0; // cur position while(!p1.empty() && !p2.empty()){ //llabs(cur-p1.top().first) if(cur > p1.top().first && llabs(cur-p2.top().first)+llabs(p2.top().second-p2.top().first)+llabs(p2.top().second-p1.top().first) <= llabs(cur-p1.top().first)){ //找看看有沒有有用的逆向的 -> 先逆向再去順向的cost <= 直接去順向cost if(DEBUG) cout << "Case0\n"; pll now = p2.top(); p2.pop(); dis += llabs(now.first - cur); dis += llabs(now.second - now.first); cur = now.second; } else if(p1.top().second <= p2.top().first){ // 順向的Ei <= 逆向的Si -> 直接順向 if(DEBUG) cout << "Case1\n"; pll now = p1.top(); p1.pop(); dis += llabs(now.first - cur); dis += llabs(now.second - now.first); cur = now.second; } else if(p1.top().first >= p2.top().first){ // 順向的Si >= 逆向的Si -> 直接逆向 if(DEBUG) cout << "Case2\n"; pll now = p2.top(); p2.pop(); dis += llabs(now.first - cur); dis += llabs(now.second - now.first); cur = now.second; } else{ // 順向的Ei > 逆向的Si -> 搬順向到逆向的Si 然後搬逆向 if(DEBUG) cout << "Case3\n"; pll now1 = p1.top(); p1.pop(); // 順向 pll now2 = p2.top(); p2.pop(); // 逆向 dis += llabs(now1.first - cur); dis += llabs(now2.first - now1.first); dis += llabs(now2.second - now2.first); cur = now2.second; p1.push({now2.first, now1.second}); // 新的 } if(DEBUG) cout << "dis: " <<dis << " cur: "<<cur<<'\n'; } while(!p1.empty()){ if(DEBUG) cout << "Case4\n"; pll now = p1.top(); p1.pop(); dis += llabs(now.first - cur); dis += llabs(now.second - now.first); cur = now.second; if(DEBUG) cout << "dis: " <<dis << " cur: "<<cur<<'\n'; } while(!p2.empty()){ if(DEBUG) cout << "Case5\n"; pll now = p2.top(); p2.pop(); dis += llabs(now.first - cur); dis += llabs(now.second - now.first); cur = now.second; if(DEBUG) cout << "dis: " <<dis << " cur: "<<cur<<'\n'; } // 走到m dis += llabs(m-cur); cout << dis << '\n'; return 0; }
Editor is loading...