正题
题目链接:https://www.ybtoj.com.cn/problem/643
题目大意
n
n
n个机器人,第
i
i
i个攻击力为
A
i
A_i
Ai,防御为
D
i
D_i
Di。
然后你每次可以对一个机器人造成
A
t
k
Atk
Atk点伤害,之后所有机器人对你进行一次攻击。
开局可以删除两个机器人,求最少受到多少伤害。
n ∈ [ 3 , 3 × 1 0 5 ] , A i , T i ∈ [ 1 , 1 0 4 ] n\in[3,3\times 10^5],A_i,T_i\in[1,10^4] n∈[3,3×105],Ai,Ti∈[1,104]
解题思路
设每个机器人需要攻击的次数
T
i
T_i
Ti
先不考虑删除的话是一个很经典的贪心,按照
T
i
A
i
\frac{T_i}{A_i}
AiTi从小到大排序就好了。证明的话
设目前是排序好的序列,是否交换相邻的两个 i , j ( j > i ) i,j(j>i) i,j(j>i)需要满足
T i A j ≥ T j A i T_iA_j\geq T_jA_i TiAj≥TjAi
化简一下就可以发现一定不合法
然后考虑删除哪两个,设
S
t
i
=
∑
j
=
1
i
T
i
,
S
a
i
=
∑
j
=
1
n
A
i
St_i=\sum_{j=1}^iT_i,Sa_i=\sum_{j=1}^nA_i
Sti=∑j=1iTi,Sai=∑j=1nAi,那么删除一个
x
x
x会减少贡献
b
x
=
(
S
a
n
−
S
a
x
)
T
x
+
S
t
x
A
x
−
A
x
b_x=(Sa_n-Sa_x)T_x+St_xA_x-A_x
bx=(San−Sax)Tx+StxAx−Ax
(分别计算自己减去的和自己对后面的数产生的贡献)。
但是如果删除了两个数 x , y ( x < y ) x,y(x<y) x,y(x<y)就会多减去 T x A y T_xA_y TxAy的贡献。
所以我们要求
max
{
b
x
+
b
y
−
T
x
A
y
}
(
x
<
y
)
\max\{ b_x+b_y-T_xA_y \} (x<y)
max{bx+by−TxAy}(x<y)
这个因为值域比较小直接上李超树就好了,当然也可以
C
D
Q
CDQ
CDQ分治或者
S
p
l
a
y
Splay
Splay搞斜率优化
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=3e5+10;
struct node{
ll b,k;
};
ll n,atk,sum,ans,maxs,lim;
ll p[N],a[N],t[N],st[N],sa[N],b[N],w[N];
bool cmp(ll x,ll y)
{return t[x]*a[y]<t[y]*a[x];}
ll ct(ll x,ll id)
{return t[p[id]]*x+b[id];}
void Change(ll x,ll l,ll r,ll id){
if(ct(l,id)>=ct(l,w[x])&&ct(r,id)>=ct(l,w[x])){w[x]=id;return;}
if(ct(l,id)<=ct(l,w[x])&&ct(r,id)<=ct(r,w[x]))return;
if(l==r)return;ll mid=(l+r)>>1;
if(t[p[id]]<t[p[w[x]]]){
if(ct(mid,id)>=ct(mid,w[x]))
Change(x*2+1,mid+1,r,w[x]),w[x]=id;
Change(x*2,l,mid,id);
}
else{
if(ct(mid,id)>=ct(mid,w[x]))
Change(x*2,l,mid,w[x]),w[x]=id;
Change(x*2+1,mid+1,r,id);
}
return;
}
ll Ask(ll x,ll l,ll r,ll pos){
if(l==r)return ct(pos,w[x]);
ll mid=(l+r)>>1,ans;
if(pos<=mid)ans=Ask(x*2,l,mid,pos);
else ans=Ask(x*2+1,mid+1,r,pos);
return max(ans,ct(pos,w[x]));
}
signed main()
{
freopen("fittest.in","r",stdin);
freopen("fittest.out","w",stdout);
scanf("%lld%lld",&n,&atk);
for(ll i=1;i<=n;i++){
scanf("%lld%lld",&a[i],&t[i]);
t[i]=(t[i]+atk-1)/atk;p[i]=i;
sum+=a[i];lim=max(max(a[i],t[i]),lim);
}
sort(p+1,p+1+n,cmp);b[0]=-1e18;
for(ll i=1;i<=n;i++){
ll x=p[i];
st[i]=st[i-1]+t[x];
sa[i]=sa[i-1]+a[x];
b[i]=(sum-sa[i])*t[x]+st[i]*a[x]-a[x];
ans+=st[i]*a[x]-a[x];
}
for(ll i=1;i<=n;i++){
int x=p[i];
ll tmp=b[i]+Ask(1,1,lim,a[x]);
maxs=max(maxs,tmp);t[x]=-t[x];
Change(1,1,lim,i);
}
printf("%lld\n",ans-maxs);
return 0;
}