1 条题解

  • 0
    @ 2026-3-18 19:20:22

    我感觉这题有必要发一篇代码(不读题错了 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
    上传者