题目分析

设 $b_i$为人形兵器 $i$被打多少次就会死。假设不能瞬间秒杀两个人形兵器，那么要按什么顺序杀人形兵器呢？（这不就是国王游戏吗？）

假设和在目前的序列中 $(a,b)$和 $(a’,b’)$是相邻的，则 $(a,b)$能够放在前面的条件是：（设 $B$为他们两个之前的 $b$的和）

$$a(B+b)+a ‘ (B+b+b ‘ ) < a ' (B+b ' )+a(B+b+b ' )$$
也就是：$\frac{b}{a}<\frac{b '}{a '}$，

则可以减少的总伤害为：

$$Sa_{i+1}b_i+(Sb_i-1)a_i+Sa_{j+1}b_j+(Sb_j-1)a_j-a_jb_i$$

将其看做一个常数加上斜率为 $-a_j$，截距为 $Sa_{j+1}b_j+(Sb_j-1)a_j$的一次函数，则所有的 $j$可以看做若干条线段，要求 $x=b_i$时的最高点。

从后往前加入线段，李超线段树维护。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
typedef long long LL;
const int N=300005;
int n,ATK,flag[N<<2];LL ans,sum;
LL Sa[N],Sb[N],B[N<<2],K[N<<2];
struct node{int a,b;}d[N];

void insert(int s,int t,int i,LL k,LL b) {
    if(!flag[i]) {K[i]=k,B[i]=b,flag[i]=1;return;}
    int mid=(s+t)>>1;
    LL l1=1LL*s*k+b,l2=1LL*s*K[i]+B[i],r1=1LL*t*k+b,r2=1LL*t*K[i]+B[i];
    LL m1=1LL*mid*k+b,m2=1LL*mid*K[i]+B[i];
    if(l1<=l2&&r1<=r2) return;
    if(l1>l2&&r1>r2) {K[i]=k,B[i]=b;return;}
    if(l1>l2) {
        if(m1>m2) insert(mid+1,t,(i<<1)|1,K[i],B[i]),K[i]=k,B[i]=b;
        else insert(s,mid,i<<1,k,b);
    }
    else {
        if(m1>m2) insert(s,mid,i<<1,K[i],B[i]),K[i]=k,B[i]=b;
        else insert(mid+1,t,(i<<1)|1,k,b);
    }
}
LL query(int x,int s,int t,int i) {
    if(s==t) return 1LL*x*K[i]+B[i];
    int mid=(s+t)>>1;LL re=1LL*x*K[i]+B[i];
    if(x<=mid) re=max(re,query(x,s,mid,i<<1));
    else re=max(re,query(x,mid+1,t,(i<<1)|1));
    return re;
}

int cmp(node x,node y) {return 1LL*y.a*x.b<1LL*x.a*y.b;}
LL getK(int x) {return -d[x].a;}
LL getB(int x) {return 1LL*Sa[x+1]*d[x].b+1LL*(Sb[x]-1)*d[x].a;}
int main()
{
    n=read(),ATK=read();
    for(RI i=1;i<=n;++i) d[i].a=read(),d[i].b=(read()-1)/ATK+1;
    sort(d+1,d+1+n,cmp);
    for(RI i=n;i>=1;--i) Sa[i]=Sa[i+1]+d[i].a;
    for(RI i=1;i<=n;++i) Sb[i]=Sb[i-1]+d[i].b;
    for(RI i=1;i<=n;++i) sum+=1LL*d[i].a*(Sb[i]-1);
    insert(1,10000,1,getK(n),getB(n)),ans=sum;
    for(RI i=n-1;i>=1;--i) {
        LL kl=query(d[i].b,1,10000,1);
        ans=min(ans,sum-(getB(i)+kl));
        insert(1,10000,1,getK(i),getB(i));
    }
    printf("%lld\n",ans);
    return 0;
}