over 3 years ago

题目很恶心……

注意僵尸是可以复活的。新加的僵尸排在最前面

但是做的时候依旧是从后面添僵尸

【具体看gty的题解……】

很明显可以维护一个凸壳。点坐标为(i*d,sum[i])

查询的时候只需要找(xi+i*d,sum[i])与点j斜率最大的即可

下凸壳

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define kk I64d
#define maxn 100001
#define eps 1e-6
using namespace std;
long double result=0.0;
int stack[maxn];
long long d;int n,top=0;
long long a[maxn]={0},sum[maxn]={0},x[maxn]={0};
long long readln()
{
    char c=getchar();long long result=0;int  bj=1;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
double fabs(double a)
{
    if (a>0) return a; else return -a;
}
int dcmp(double a,double b)
{
    if (fabs(a-b)<eps) return 0;
    if (a>b) return 1;else return -1;
}
double xl(int a,int b)
{
    return (sum[a]-sum[b-1])/(x[a]+d*a-d*b);
}
double xltb(int a,int b)
{
    return (sum[a-1]-sum[b-1])/(d*a-d*b);
}
int find(int left,int right,int k)
{
    int lmid,rmid;
    while (left+1<right)
    {
        lmid=left+(right-left+1)/3;rmid=left+(right-left+1)*2/3;
        if (dcmp(xl(k,lmid),xl(k,rmid))>0) right=rmid-1;
        else left=lmid+1;
    }
    if (dcmp(xl(k,left),xl(k,right))>0) return left;
    else return right;
}
int main()
{
    int i,k;
    n=readln();d=readln();
    for (i=1;i<=n;i++)
    {
        a[i]=readln();x[i]=readln();sum[i]=sum[i-1]+a[i];
    }
    for (i=1;i<=n;i++)
      {
        while (top>=2&&dcmp(xl(i,stack[top-1]),xl(i,stack[top]))<0) top--;
        stack[++top]=i;
        k=find(1,top,i);
        result+=(sum[i]-sum[k-1])/(long double)(x[i]+d*i-d*k);
      }
    printf("%d\n",(int)(result+0.5));
}
← 【bzoj1011】【公式】【精度】遥远的行星 【bzoj1011】【公式】【精度】遥远的行星 →
 
comments powered by Disqus