正題

題目鏈接:https://www.ybtoj.com.cn/problem/643

---

題目大意

$n$個機器人，第$i$個攻擊力為$A_i$，防御為$D_i$。
然后你每次可以對一個機器人造成$Atk$點傷害，之后所有機器人對你進行一次攻擊。

開局可以刪除兩個機器人，求最少受到多少傷害。

$n\in [3,3\times 10^5],A_i,T_i\in [1,10^4]$

---

解題思路

設每個機器人需要攻擊的次數$T_i$
先不考慮刪除的話是一個很經典的貪心，按照$\frac{T_i}{A_i}$從小到大排序就好了。證明的話

設目前是排序好的序列，是否交換相鄰的兩個$i,j(j>i)$需要滿足
$$T_i{A}_j\ge T_j{A}_i$$
化簡一下就可以發現一定不合法

然后考慮刪除哪兩個，設$S{t}_i={\sum }_{j=1}^i{T}_i,S{a}_i={\sum }_{j=1}^n{A}_i$，那么刪除一個$x$會減少貢獻
$$b_x=(S{a}_n?S{a}_x)T_x+S{t}_x{A}_x?A_x$$
（分別計算自己減去的和自己對后面的數產生的貢獻）。

但是如果刪除了兩個數$x,y(x<y)$就會多減去$T_x{A}_y$的貢獻。

所以我們要求$$\max \{b_x+b_y?T_x{A}_y\}(x<y)$$
這個因為值域比較小直接上李超樹就好了，當然也可以$CDQ$分治或者$Splay$搞斜率優化

時間復雜度$O(n\log n)$

---

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; }

總結

以上是生活随笔為你收集整理的YbtOJ#643-机器决斗【贪心,李超树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。