Lazy Salesgirl ZOJ - 3606

​​點選打開連結​​

先把每個人按其與之前一個人的時間差排序 然後更新線段樹對應時間點的位置 因為目前時間間隔比之前的都長 那之前的肯定也都滿足

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long

struct node1
{
    int time;
    ll cost;
    int gap;
    int id;
};

struct node2
{
    int l;
    int r;
    ll val[5];
    int cnt;
};

node1 per[100010];
node2 tree[800010];
int n;

bool cmpI(node1 n1,node1 n2)
{
    return n1.time<n2.time;
}

bool cmpII(node1 n1,node1 n2)
{
    return n1.gap<n2.gap;
}

void pushup(int cur)
{
    int i,p;
    for(i=0;i<3;i++)
    {
        p=(i+tree[2*cur].cnt)%3;
        tree[cur].val[i]=tree[2*cur].val[i]+tree[2*cur+1].val[p];
    }
    tree[cur].cnt=tree[2*cur].cnt+tree[2*cur+1].cnt;
    return;
}

void build(int l,int r,int cur)
{
    int m;
    tree[cur].l=l;
    tree[cur].r=r;
    tree[cur].val[0]=0;
    tree[cur].val[1]=0;
    tree[cur].val[2]=0;
    tree[cur].cnt=0;
    if(l==r) return;
    m=(l+r)/2;
    build(l,m,2*cur);
    build(m+1,r,2*cur+1);
    return;
}

void update(int tar,ll val,int cur)
{
    int i;
    if(tree[cur].l==tree[cur].r)
    {
        for(i=0;i<3;i++)
        {
            tree[cur].val[i]=(i+1)*val;
        }
        tree[cur].cnt++;
        return;
    }
    if(tar<=tree[2*cur].r) update(tar,val,2*cur);
    else update(tar,val,2*cur+1);
    pushup(cur);
    return;
}

int main()
{
    double ans1,ans2;
    ll a,b,ta,tb;
    int t,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&per[i].cost);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&per[i].time);
        }
        sort(per+1,per+n+1,cmpI);
        for(i=1;i<=n;i++)
        {
            per[i].gap=per[i].time-per[i-1].time;
            per[i].id=i;
        }
        sort(per+1,per+n+1,cmpII);
        memset(tree,0,sizeof(tree));
        build(1,n,1);
        a=0,b=n;
        for(i=1;i<=n;)
        {
            j=i;
            while(j<=n&&per[i].gap==per[j].gap)
            {
                update(per[j].id,per[j].cost,1);
                j++;
            }
            ta=tree[1].val[0],tb=j-1;
            if(a*tb<b*ta)
            {
                ans1=1.0*per[i].gap;
                a=ta;
                b=tb;
            }
            i=j;
        }
        ans2=1.0*a/b;
        printf("%.6f %.6f\n",ans1,ans2);
    }
    return 0;
}