伦敦做网站,电子商务网站建设复习题,烟台网站定制排名,深圳公司排名查询我三分这么好吗居然1A啦#xff1f;#xff1f;#xff1f;提交的时候只是想着先WA一次的。。。。 这题真的很妙啊 首先第一步#xff0c;就是把僵尸的生命值取一个前缀和#xff0c;这样造成伤害的时候#xff0c;可以视为同时对所有僵尸造成伤害。 那么就可以得到一个柿…我三分这么好吗居然1A啦提交的时候只是想着先WA一次的。。。。 这题真的很妙啊 首先第一步就是把僵尸的生命值取一个前缀和这样造成伤害的时候可以视为同时对所有僵尸造成伤害。 那么就可以得到一个柿子 对于第i次进攻kmax( (sum[i]-sum[j-1]) / x[i](i-j)*d ) 其中j表示第j只僵尸。 这样时间的复杂度是O(n^2)的妥妥的过不去 然后设y1sum[i],y2sum[j-1] x1x[i]i*d,x2j*d 柿子就变成了k(y1-y2)/(x1-x2)这不就是斜率吗 令P(x1,y1),Q(x2,y2)可以发现Q一直是不变的变的只是P值得注意的是P的x坐标没有单调性 那么对于Q每次加入用单调栈维护一个下凸包三分答案出解即可 #includecstdio
#includeiostream
#includecstring
#includecstdlib
#includealgorithm
#includecmath
using namespace std;double sum[110000],w[110000];
struct node
{double x,y;
}sta[110000];int top;
double slope(node n1,node n2){return (n1.y-n2.y)/(n1.x-n2.x);}
int main()
{int n;double d;scanf(%d%lf,n,d);double ans0;sum[0]0;top0;for(int i1;in;i){scanf(%lf%lf,sum[i],w[i]);sum[i]sum[i-1];node Q;Q.xdouble(i)*d,Q.ysum[i-1];while(top!0slope(sta[top-1],sta[top])slope(sta[top],Q))top--;sta[top]Q; node P;P.xw[i]double(i)*d,P.ysum[i];int l1,rtop;while(r-l3){int mid(lr)/2;int mmid(midr)/2;if(slope(P,sta[mid])slope(P,sta[mmid])){rmmid-1;}else lmid1;}int ipl;for(int jl1;jr;j)if(slope(P,sta[j])slope(P,sta[ip]))ipj;ansslope(P,sta[ip]);}printf(%.0lf\n,ans);return 0;
} 转载于:https://www.cnblogs.com/AKCqhzdy/p/8909010.html
