代码

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

const int MAXN=1e6+128;

pair <int,int> Data[MAXN];

set < pair <int ,int > > Base;

int main()
{
    //freopen("/home/noilinux/Desktop/day1_B/card/card3.in","r",stdin);
    int n,m;
    scanf(" %d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf(" %d",&Data[i].first);
    }
    for(int i=1;i<=n;i++)
    {
        scanf(" %d",&Data[i].second);
    }
    Base.insert(Data+1,Data+1+n);

    int ans=(Base.rbegin()).first-(Base.begin()).first;
    for(int i=0;i<m;i++)
    {
        int l=max((Base.begin()).second,(Base.rbegin()).first)-min((Base.begin()).second,(++Base.begin()).first);//翻转左边的新解
        int r=max((Base.rbegin()).second,(++Base.rbegin()).first)-min((Base.begin()).first,(Base.rbegin()).second);//同上

        if(l>=ans && r>=ans)    //无更优解
        {
            break;
        } else
        if(l<r)     //翻转左边更有利
        {
           pair< int ,int > t=*(Base.begin());
           Base.erase(Base.begin());
            swap(t.first,t.second);
            Base.insert(t);
        }   else    {
           pair< int ,int > t=*--Base.end();
           Base.erase(--Base.end());
            swap(t.first,t.second);
            Base.insert(t);
        }
        ans=min(l,r);
    }
    printf("%d",ans);
}

Last modification:April 18th, 2021 at 11:51 am