P3299 [SDOI2013]保护出题人

全世界都会二分可海星……

首先记\(sum[i]\)为\(a[i]\)的前缀和，那么第\(i\)个的答案就是\(max\{\frac{sum[i]-sum[j-1]}{x+(i-j)d}\}\)，那么我们可以把式子给看做点\((j*d,sum[j-1])\)和\((x+i*d,sum[i])\)的斜率。发现前面那个是一个定值，于是我们可以维护一个下凸包，因为凸包上的斜率单调增，每一次在这个凸包上二分最大的斜率即可

//minamoto

#include<bits/stdc++.h>

#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)

#define ll long long

#define eps 1e-3

using namespace std;

#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

char buf[1<<21],*p1=buf,*p2=buf;

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

ll read(){

    ll res,f=1;char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=1e5+5;

int n,top,l,r,mid,ret;ll d,a[N],sum[N],x[N];double ans;

struct node{ll x,y;}st[N],res;

inline double slope(const node &a,const node &b){return 1.0*(b.y-a.y)/(b.x-a.x);}

int main(){

//	freopen("testdata.in","r",stdin);

	n=read(),d=read();

	fp(i,1,n)a[i]=read(),x[i]=read(),sum[i]=sum[i-1]+a[i];

	fp(i,1,n){

		res={d*i,sum[i-1]};

		while(top&&slope(st[top-1],st[top])>slope(st[top],res))--top;

		st[++top]=res,res={x[i]+d*i,sum[i]};

		l=1,r=top;

		while(l<=r){

			mid=(l+r)>>1;

			(slope(st[mid],res)>slope(st[mid-1],res))?l=mid+1,ret=mid:r=mid-1;

		}ans+=slope(st[ret],res);

	}printf("%.0lf\n",ans);return 0;

}

巴特西

P3299 [SDOI2013]保护出题人

最新文章

热门文章