题目描述

数据范围

解法

三分找出极值，两个二分找出极值的范围。

代码

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define ll long long

using namespace std;

const char* fin="linear.in";

const char* fout="linear.out";

const ll inf=0x7fffffff;

const ll maxn=100007,maxa=1000000007;

ll n,m,i,j,k,l,r,mid,mmid,tmp,tmd;

ll a[maxn][2];

ll count(ll v){

    ll i,j,k=0;

    for (i=1;i<=n;i++){

        if (v>a[i][1]) k+=v-a[i][1];

        else if (v<a[i][0]) k+=a[i][0]-v;

    }

    return k;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%d",&n);

    for (i=1;i<=n;i++) scanf("%d%d",&a[i][0],&a[i][1]);

    l=0;

    r=maxa-1;

    while (l<r){

        mid=(l+r)/2;

        mmid=(mid+r)/2;

        if (mid==mmid){

            break;

        }

        tmp=count(mid);

        tmd=count(mmid);

        if (tmp<tmd) r=mmid;

        else if (tmp>tmd) l=mid;

        else{

            l=mid;

            r=mmid;

        }

    }

    k=l;

    for (;l<=r;l++){

        if (count(l)<count(k)) k=l;

    }

    tmp=count(k);

    l=0;

    r=k;

    while (l<r){

        mid=(l+r)/2;

        if (count(mid)>tmp) l=mid+1;

        else r=mid;

    }

    printf("%lld ",l);

    l=k;

    r=maxa-1;

    while (l<r){

        mid=(l+r+1)/2;

        if (count(mid)>tmp) r=mid-1;

        else l=mid;

    }

    printf("%lld\n",l);

    return 0;

}

启发

三分时当l,r距离小于3时，就可以break了，随后，暴力求解。

比赛中我运用了演绎很快解决了题目。

即猜测f(y)具有三分性。

事实上这道题是可以分析出三分的：

首先预设O(maxa)的费用，将问题转化为某一个f(y)的值。

考虑答案贡献的来源，对于每一个xi，都有|xi-y|这样的贡献。

事实上随着y的增大，这些贡献会先减少，减少到0后增多。

设对于y到y+1的增量为delta，那么delta就是增量和-减量和。

显然，随着y的增大，增量会不断增加，减量会不断减少。

显然delta<0时，f(y)呈下降趋势；

delta=0时，f(y)呈平台；

delta>0时，f(y)呈上升趋势。

总体呈抛物平台状，满足三分性。

引入第二种类型的优化：单调优化；

具体表现为二分、三分等。

显然可以将预设的费用降到O(logmaxa)，再加上O(n)求答案。

总的时间复杂度为O(nlogmaxa)。