【堆】Facer帮爹

题目链接

上凸二次函数问题,先求顶点,然后逐步逼近问题的解

用小根堆维护 $x$ 改变时的 $\Delta y$

while(票数超过) --x[i],v=newval(),down();

如果一开始票数就满足要求,就直接输出

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=1e5+5;

int n,m,sum;
int a[MAXN],b[MAXN],v[MAXN],hp[MAXN],ct[MAXN];
long long ans;

inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||'9'<ch) ch=getchar();
    while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    return x;
}

int tip(int a,int b){return (int)(1.0*a/(b<<1)+0.5);}
int val(int a,int b,int x){return a+b-(b<<1)*x;}

void ins(int x)
{
    hp[++hp[0]]=x;
    for(int i=hp[0],j=hp[0]>>1;j;i=j,j>>=1){
        if(v[hp[i]]<v[hp[j]]) swap(hp[i],hp[j]);
        else break;
    }return;
}

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        a[i]=read(),b[i]=read();
        if(a[i]<=b[i]) {--i,--n;continue;}
        ct[i]=tip(a[i],b[i]);
        sum+=ct[i];
        v[i]=val(a[i],b[i],ct[i]);
        ins(i);
    }return;
}

void write()
{
    for(int i=1;i<=n;++i) ans+=(a[i]-(long long)ct[i]*b[i])*ct[i];
    printf("%lld\n",ans);return;
}

void down()
{
    for(int i=1,j=2;j<=hp[0];i=j,j<<=1){
        if(j<hp[0]&&v[hp[j+1]]<v[hp[j]]) ++j;
        if(v[hp[i]]>v[hp[j]]) swap(hp[i],hp[j]);
        else break;
    }return;
}

void pop()
{
    hp[1]=hp[hp[0]--];
    down();return;
}

void solve()
{
    while(sum>m){
        --ct[hp[1]],--sum;
        v[hp[1]]=val(a[hp[1]],b[hp[1]],ct[hp[1]]);
        if(!ct[hp[1]]) pop();
        else down();
    }return;
}

int main()
{
    init();
    if(sum<=m){write();return 0;}
    solve();
    write();
    return 0;
}