1 条题解
-
0
我感觉这题有必要发一篇代码(不读题错了 N 次):
#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+10; struct node1{int l,r;bool friend operator<(node1 n1,node1 n2){return n1.l!=n2.l?n1.l>n2.l:n1.r>n2.r;}}; struct node2{int l,r;bool friend operator<(node2 n1,node2 n2){return n1.r!=n2.r?n1.r<n2.r:n1.l<n2.l;}}; multiset<node1>s1;multiset<node2>s2; node1 a[N]; signed main() { int n;cin>>n;int bk1=0,bk2=0; for(int i=1;i<=n;i++) { int x,y;cin>>x>>y; a[i]={x,y}; if(x>0)bk2=1;if(y<0)bk1=1; } int ans=0,sum,bk,pos; sum=0;bk=0;pos=0; s1.clear();s2.clear(); for(int i=1;i<=n;i++)s1.insert({a[i].l,a[i].r}),s2.insert({a[i].l,a[i].r}); while(s1.size()) { if(bk) { auto it=s1.begin();node1 no=*it; if(pos<no.l)sum+=no.l-pos,pos=no.l; else if(pos>no.r)sum+=pos-no.r,pos=no.r; auto it1=s2.lower_bound({no.l,no.r}); s1.erase(it);s2.erase(it1); } else { auto it=s2.begin();node2 no=*it; if(pos<no.l)sum+=no.l-pos,pos=no.l; else if(pos>no.r)sum+=pos-no.r,pos=no.r; auto it1=s1.lower_bound({no.l,no.r}); s1.erase(it1);s2.erase(it); } bk^=1; } if(bk1)ans=max(ans,sum+abs(pos)); sum=0;bk=1;pos=0; s1.clear();s2.clear(); for(int i=1;i<=n;i++)s1.insert({a[i].l,a[i].r}),s2.insert({a[i].l,a[i].r}); while(s1.size()) { if(bk) { auto it=s1.begin();node1 no=*it; if(pos<no.l)sum+=no.l-pos,pos=no.l; else if(pos>no.r)sum+=pos-no.r,pos=no.r; auto it1=s2.lower_bound({no.l,no.r}); s1.erase(it);s2.erase(it1); } else { auto it=s2.begin();node2 no=*it; if(pos<no.l)sum+=no.l-pos,pos=no.l; else if(pos>no.r)sum+=pos-no.r,pos=no.r; auto it1=s1.lower_bound({no.l,no.r}); s1.erase(it1);s2.erase(it); } bk^=1; } if(bk2)ans=max(ans,sum+abs(pos)); cout<<ans; return 0; }
- 1
信息
- ID
- 8659
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 12
- 已通过
- 2
- 上传者