AC日记——松江1843路 洛谷七月月赛

松江1843路

思路：

　　三分；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 100005

#define ll long long

struct DataType

{

    ll pi,val,sumval,sumpi;

    bool operator<(const DataType pos)const

    {

        return pi<pos.pi;

    }

};

struct DataType ai[maxn];

ll len,n;

inline void in(ll &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'')Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

ll lower(ll key)

{

    ll l=,r=n,res=,mid;

    while(l<=r)

    {

        mid=l+r>>;

        if(key<=ai[mid].pi) res=mid,r=mid-;

        else l=mid+;

    }

    return res;

}

ll calculate(ll key)

{

    ll now=lower(key);

    ll res1=key*ai[now-].sumval-ai[now-].sumpi;

    ll res2=ai[n].sumpi-ai[now-].sumpi-key*(ai[n].sumval-ai[now-].sumval);

    return res2+res1;

}

int main()

{

    in(len),in(n);

    for(ll i=;i<=n;i++) in(ai[i].pi),in(ai[i].val);

    sort(ai+,ai+n+);

    for(ll i=;i<=n+;i++)

    {

        ai[i].sumval=ai[i-].sumval+ai[i].val;

        ai[i].sumpi=ai[i-].sumpi+ai[i].val*ai[i].pi;

    }

    ll l=,r=len,mid,now,nowl,nowr;

    while(l<r)

    {

        mid=l+r>>;

        now=calculate(mid);

        nowl=calculate(mid-);

        nowr=calculate(mid+);

        if(nowl<now) r=mid-;

        else if(nowr<now) l=mid+;

        else

        {

            printf("%lld\n",calculate(mid));

            return ;

        }

    }

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

    return ;

}