BZOJ 4700: 适者 December 1, 2016 ###Description 敌方有n台人形兵器，每台的攻击力为Ai，护甲值为Di。我方只有一台人形兵器，攻击力为ATK。战斗看作回合制， 每回合进程如下： ·1 我方选择对方某台人形兵器并攻击，令其护甲值减少ATK，若护甲值<0则被破坏。 ·2 敌方每台未被破坏的人形兵器攻击我方基地造成Ai点损失。 但是，在第一回合开始之前，某两台敌方的人形兵器被干掉了(秒杀）。问最好情况下，我方基地会受到多少点损 失。 ###Input 第一行两个数n，ATK，表示敌方人形兵器数量和我方人形兵器攻击力。 接下来n行，每行两个数A，Di，表示对方第i台人形兵器的攻击力和护甲值。 3<=n<=3×10^5，Ai，Di<=10^4，ATK<10^4 ###Output 只一行，一个数，表示最好情况下我方基地会受到的损失总和。 ###Sample Input 3 7 30 8 7 35 1 209 ###Sample Output 28 ###Solution 每个敌人被杀所需时间为 Ti=Di/atk+1 设T的前缀和为P，A的后缀和为S 假设没有秒杀，按Ti/Ai排序后依次杀即可，每个敌人对答案的贡献为Si\*Ti-Ai 假设（排序后）秒杀了i和j（假设i<j） 那么我方损失会减少 Si\*Ti + P(i-1)\*Ai - Ai + Sj\*Tj + P(j-1)\*Aj - Aj - Ti\*Aj 注意最后 -Ti\*Aj 是因为算了两次 由于只有 Ti\*Aj 与 i,j 均有关，这个表达式可以看成一个以Ti为变量的一次函数 若从后往前扫，就可以看成动态维护一些直线的凸包 这个用线段树就可以维护，每个节点存一条直线，标记永久化 修改时，找到两直线交点，把距端点更短的一部分pushdown 查询时把路径上所有节点取max ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) struct line { ll k,b; }s[35000]; void modify(int x,int l,int r,line p) { if(s[x].k==p.k) { repr(s[x].b,p.b); return; } int t=(l+r)>>1; db f=(db)(p.b-s[x].b)/(s[x].k-p.k); if(f<l||f>r||l==r) { if(p.k*t+p.b>s[x].k*t+s[x].b)s[x]=p; return; } if(f<t+0.5) { if(p.k*r+p.b>s[x].k*r+s[x].b)std::swap(s[x],p); modify(x<<1,l,t,p); } else { if(p.k*l+p.b>s[x].k*l+s[x].b)std::swap(s[x],p); modify(x<<1|1,t+1,r,p); } } ll query(int x,int l,int r,int p) { ll ret=s[x].k*p+s[x].b; if(l!=r) { int t=(l+r)>>1; if(p<=t) repr(ret,query(x<<1,l,t,p)); else repr(ret,query(x<<1|1,t+1,r,p)); } return ret; } struct yjq { int a,t; ll as,tp; inline bool operator <(const yjq &x)const { return (ll)x.a*t<(ll)a*x.t; } }p[300000]; int n,atk; int main() { scanf("%d%d",&n,&atk); for(int i=0;i<n;i++) scanf("%d%d",&p[i].a,&p[i].t),p[i].t=(p[i].t-1)/atk+1; std::sort(p,p+n); for(int i=1;i<n;i++) p[i].tp=p[i-1].tp+p[i-1].t; p[n-1].as=p[n-1].a; for(int i=n-2;i>=0;i--) p[i].as=p[i+1].as+p[i].a; for(int i=0;i<35000;i++) s[i].b=-1e18; ll ta=0; for(int i=n-1;i>=0;i--) { ll tmp=p[i].as*p[i].t+p[i].tp*p[i].a-p[i].a; repr(ta,query(1,1,10000,p[i].t)+tmp); modify(1,1,10000,(line){-p[i].a,tmp}); } ll ans=0; for(int i=0;i<n;i++) ans+=p[i].as*p[i].t-p[i].a; ans-=ta; printf("%lld\n",ans); } ```