2017-10-04清北模拟赛

T1 财富(treasure)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK有n个小伙伴。每个小伙伴有一个身高hi。

这个游戏是这样的，LYK生活的环境是以身高为美的环境，因此在这里的每个人都羡慕比自己身高高的人，而每个人都有一个属性ai表示它对身高的羡慕值。

这n个小伙伴站成一列，我们用hi来表示它的身高，用ai来表示它的财富。

每个人向它的两边望去，在左边找到一个最近的比自己高的人，然后将ai朵玫瑰给那个人，在右边也找到一个最近的比自己高的人，再将ai朵玫瑰给那个人。当然如果没有比自己身高高的人就不需要赠送别人玫瑰了。也就是说一个人会给0,1,2个人玫瑰（这取决于两边是否有比自己高的人）。

每个人都会得到若干朵玫瑰（可能是0朵），LYK想知道得了最多的玫瑰的那个人得了多少玫瑰。(然后嫁给他>3<)

输入格式(treasure.in)

    第一行一个数n表示有n个人。

    接下来n行，每行两个数hi,ai。

输出格式(treasure.out)

    一个数表示答案。

输入样例

3

4 7

3 5

6 10

输出样例

12

样例解释

第一个人会收到5朵玫瑰，第二个没人送他玫瑰，第三个人会收到12朵玫瑰。

数据范围

对于50%的数据n<=1000,hi<=1000000000。

对于另外20%的数据n<=50000，hi<=10。

对于100%的数据1<=n<=50000,1<=hi<=1000000000。1<=ai<=10000。

/*
o(n)每个点向左找一个最近的且比它大的，
o(n)每个点向右找一个最近的且比他大的
f[i]第i个人收到的玫瑰数
Stack[i]在单调的数列中第i个位置是n个人中的哪个人
求最靠近它且比它高的那个位置是哪个
O(n)
*/
#include <cstdio>

#define LL long long
inline void read(LL &x)
{
    x=0; register char ch=getchar();
    for(; ch>'9'||ch<'0'; ) ch=getchar();
    for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
}
const int N(50005);
LL n,h[N],v[N],f[N],ans;
int Stack[N],top;

int Presist()
{
//    freopen("treasure.in","r",stdin);
//    freopen("treasure.out","w",stdout);
    read(n);
    for(int i=1; i<=n; ++i)
        read(h[i]),read(v[i]);
    for(int i=1; i<=n; ++i)
    {
        for(; top&&h[i]>=h[Stack[top]]; ) top--;
        //=注意 
        f[Stack[top]]+=v[i];
        Stack[++top]=i;
    }    top=0;
    for(int i=n; i>=1; --i)
    {
        for(; top&&h[i]>=h[Stack[top]]; ) top--;
        f[Stack[top]]+=v[i];
        Stack[++top]=i;
    }
    for(int i=1; i<=n; ++i)
        ans=ans>f[i]?ans:f[i];
    printf("%I64d",ans); 
    return 0;
}

int Aptal=Presist();
int main(int argc,char**argv){;}

T2 正方形(square)

Time Limit:1000ms   Memory Limit:128MB

题目描述

在一个10000*10000的二维平面上，有n颗糖果。

LYK喜欢吃糖果！并且它给自己立了规定，一定要吃其中的至少C颗糖果！

事与愿违，LYK只被允许圈出一个正方形，它只能吃在正方形里面的糖果。并且它需要支付正方形边长的价钱。

LYK为了满足自己的求食欲，它不得不花钱来圈一个正方形，但它想花的钱尽可能少，你能帮帮它吗？

输入格式(square.in)

    第一行两个数C和n。

    接下来n行，每行两个数xi,yi表示糖果的坐标。

输出格式(square.out)

    一个数表示答案。

输入样例

3 4

1 2

2 1

4 1

5 2

输出样例

4

样例解释

选择左上角在(1,1)，右下角在(4,4)的正方形，边长为4。

数据范围

对于30%的数据n<=10。

对于50%的数据n<=50。

对于80%的数据n<=300。

对于100%的数据n<=1000。1<=xi,yi<=10000。

/*
求最小的代价，考虑二分（logmaxlen）
发现数据范围支持n^2logmaxlen的复杂度
现将所求正方形看做是一个无限高的矩形，
O(n)枚举一个右端点，确定出左端点后，
再O(n)判断在规定的高度内能否得到C个糖果 
*/
#include <algorithm>
#include <cstdio>

inline void read(int &x)
{
    x=0; register char ch=getchar();
    for(; ch>'9'||ch<'0'; ) ch=getchar();
    for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
}
const int N(1e3+5);

struct Pos {
    int x,y; 
    bool operator < (const Pos&a)const
    {
        return x<a.x;
    }
}pos[N];

int n,c,L,R,Mid,ans,cnt,tmp[N];
bool cmp(int a,int b) { return a<b; }
inline bool judge(int l,int r)
{
    if(r-l+1<c) return false;
    cnt=0;
    for(int i=l; i<=r; ++i)
        tmp[++cnt]=pos[i].y;
    std::sort(tmp+1,tmp+cnt+1,cmp);
    for(int i=c; i<=cnt; ++i)
        if(tmp[i]-tmp[i-c+1]<=Mid) return 1;
    return false;
}
inline bool check(int x)
{
    int l=1,r=1;
    for(; r<=n; ++r)
     if(pos[r].x-pos[l].x>x)
     {
        if(judge(l,r-1)) return true;
        for(; pos[r].x-pos[l].x>x; ) l++;
     }
    return judge(l,n);
}

int Presist()
{
    read(c),read(n);
    for(int i=1; i<=n; ++i)
        read(pos[i].x),read(pos[i].y);
    std::sort(pos+1,pos+n+1);
    for(R=10000; L<=R; )
    {
        Mid=L+R>>1;
        if(check(Mid))
        {
            R=Mid-1;
            ans=Mid+1;
        }
        else L=Mid+1;
    }
    printf("%d
",ans);
    return 0;
}

int Aptal=Presist();
int main(int argc,char**argv){;}

T3 追逐(chase)

Time Limit:1000ms   Memory Limit:128MB

题目描述

这次，LYK以一个上帝视角在看豹子赛跑。

在一条无线长的跑道上，有n只豹子站在原点。第i只豹子将在第ti个时刻开始奔跑，它的速度是vi/时刻。

因此在不同的时刻，这n只豹子可能在不同的位置，并且它们两两之间的距离也将发生变化。

LYK觉得眼光八方太累了，因此它想找这么一个时刻，使得最远的两只豹子的距离尽可能近，当然这不能是第0时刻或者第0.01时刻。它想知道的是最迟出发的豹子出发的那一刻开始，离得最远的两只豹子在距离最小的时候这个距离是多少。

当然这个时刻不仅仅可能发生在整数时刻，也就是说可能在1.2345时刻这个距离最小。

输入格式(chase.in)

    第一行一个数n。

    接下来n行，每行两个数分别是ti和vi。

输出格式(chase.out)

    输出一个数表示答案，你只需保留小数点后两位有效数字就可以了。

输入样例

3

1 4

2 5

3 7

输出样例

0.33

样例解释

在第5+2/3这个时刻，第一只豹子在18+2/3这个位置，第二只豹子在18+1/3这个位置，第三只豹子在18+2/3这个位置，最远的两只豹子相距1/3的距离，因此答案是0.33。

数据范围

对于20%的数据n=2。

对于20%的数据n=3

对于60%的数据n<=100。

对于80%的数据n<=1000。

对于100%的数据n<=100000，1<=vi,ti<=100000。

二分+计算几何。

/*
左边为1的情况下，右边是什么

随着左边向右移动，右边也一定向右移动。

左边至多移动n次，右边也至多移动n次，总共2n次。  O(n)，这个宽t至少是多少

假设绿色的最短的那根不在交点处取到。
t>mid  不可行   t<=mid  可行

求出所有交点，然后再求每只豹子在这个交点的那个时刻的位置，更新答案。
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>

using namespace std;

const long double INF=(long double)1000000000*10;
const int N(1e5+5);
long double L,R,mid,ans,hh[N];
int r,rr,i,n,MAX,X,Y,cnt,vv[N],vv2[N];
struct node2 {
    int t;
    long double l;
} s[N<<1],S[N<<1];
struct node {
    int t,v;
} t[N];
int cmp(node i,node j)
{
    return i.v<j.v || i.v==j.v && i.t>j.t;
}
struct Node
{
    long double x;
    int y,z;
} p[N<<1];
int CMP(Node i,Node j)
{
    return i.x<j.x;
}
long double work(int x,long double y)
{
    return (long double)t[x].v*y-hh[x];
}
int main()
{
    freopen("chase.in","r",stdin);
    freopen("chase.out","w",stdout);
    while (1)
    {
        scanf("%d",&n);
        // if (n==0) return 0;
        MAX=0;
        for (i=1; i<=n; i++)
        {
            scanf("%d%d",&t[i].t,&t[i].v);
            MAX=max(MAX,t[i].t);
        }
        sort(t+1,t+n+1,cmp);
        int MIN=t[n].t;
        for (i=n-1; i>=2; i--)
        {
            if (t[i].t>MIN) vv[i]=1;
            else
                MIN=t[i].t,vv[i]=0;
        }
        for (i=1; i<=n; i++) hh[i]=(long double)t[i].t*t[i].v;
        r=1;
        s[1].l=MAX;
        s[1].t=1;
        s[2].l=INF;
        vv[n]=0;
        for (i=2; i<=n; i++)
            if (!vv[i])
            {
                while (r && work(i,s[r].l)>=work(s[r].t,s[r].l)) r--;
                if (!r)
                {
                    r=1;
                    s[1].l=MAX;
                    s[1].t=i;
                    continue;
                }
                L=s[r].l;
                R=s[r+1].l;
                mid=(L+R)/2.0;
                for (int I=1; I<=80; I++)
                {
                    if (work(i,mid)>=work(s[r].t,mid))
                    {
                        R=mid;
                        mid=(L+R)/2.0;
                    }
                    else
                    {
                        L=mid;
                        mid=(L+R)/2.0;
                    }
                }
                s[++r].l=mid;
                s[r].t=i;
                s[r+1].l=INF;
            }
        rr=1;
        S[1].l=MAX;
        S[2].l=INF;
        S[1].t=n;
        MIN=t[1].t;
        for (i=2; i<n; i++)
            if (t[i].t<MIN) vv2[i]=1;
            else
                MIN=t[i].t,vv2[i]=0;
        for (i=n-1; i>=1; i--)
            if (!vv2[i])
            {
                while (rr && work(i,S[rr].l)<=work(S[rr].t,S[rr].l)) rr--;
                if (!rr)
                {
                    rr=1;
                    S[1].l=MAX;
                    S[1].t=i;
                    continue;
                }
                L=S[rr].l;
                R=S[rr+1].l;
                mid=(L+R)/2.0;
                for (int I=1; I<=80; I++)
                {
                    if (work(i,mid)<=work(S[rr].t,mid))
                    {
                        R=mid;
                        mid=(L+R)/2.0;
                    }
                    else
                    {
                        L=mid;
                        mid=(L+R)/2.0;
                    }
                }
                S[++rr].l=mid;
                S[rr].t=i;
                S[rr+1].l=INF;
            }
        cnt=0;
        for (i=1; i<=r; i++)
        {
            p[++cnt].x=s[i].l;
            p[cnt].y=1;
            p[cnt].z=s[i].t;
        }
        for (i=1; i<=rr; i++)
        {
            p[++cnt].x=S[i].l;
            p[cnt].y=0;
            p[cnt].z=S[i].t;
        }
        sort(p+1,p+cnt+1,CMP);
        X=Y=0;
        ans=INF;
        for (i=1; i<=cnt; i++)
        {
            if (p[i].y==1) X=p[i].z;
            else Y=p[i].z;
            //  printf("%.5f
",(double)p[i].x);
            if (X && Y) ans=min(ans,work(X,p[i].x)-work(Y,p[i].x));
        }
        printf("%.2f
",fabs((double)ans));
        return 0;
    }
}