百度收录网站定位地址,wordpress 检测浏览器,如何进行关键词优化工作,网站建设询价函我三分这么好吗居然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
