水题一道

题意稍微翻译下:

N个人,每个人有到的时间和离开的时间,如果在一个人到了公司并且还未离开的这段时间里有其他人来,其他人就会对这个人说How are you？

其实看看样例就懂,用什么google翻译

一开始我眼瞎,只看到这个...

只觉得N^2不就随便A吗??

然后喜闻乐见

这才看到N是10^5

咳咳

下面讲讲nlogn的正解

先认真分析一下,一个人只有还待在公司时才能被其他人问候

转换成代码大概就是

    s[i].st<=s[j].st&&s[i].ed>=s[j].st

可以看到,对于j而言,比较的都只是st（到的时间）

所以这里很容易想到将st从小到大排序.

之后再如同n^2算法一样开两层循环,不过第二层循环可以多一个break

代码如下

    for(rg int i=1;i<=n;++i)
    {
        for(rg int j=i+1;j<=n;++j)
        {
            if(s[j].st>s[i].ed) break;
            if(s[j].st<=s[i].ed) ++s[i].num;    
        }
    }

对于当前的第j个人而言,如果他到公司的时候第i个人已经离开了,那么他之后的人都比他还晚到公司,当然就没有必要进行比较.

这就是对n^2算法的一个小优化,然而还是不能过这个题

进一步思考我们可以发现,这里的st很明显满足局部舍弃性.也就是说如果对于第j个人而言都不能满足i,那么j之后的也一定不能满足.

至此,我们就可以使用二分来对最大j的值进行判断

代码如下

    for(rg int i=1;i<=n;++i)
    {
        int ans=i;
        int l=i,r=n;
        if(s[i+1].st>s[i].ed) continue;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(s[mid].st<=s[i].ed)
            {
                ans=mid;
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        s[i].num+=(ans-i);
    }

最外层1~n,二分时间复杂度logn

总体复杂度nlogn.

本题主要算法介绍到此结束,其余细节就不多解释了.主要是我懒

下面是ac代码(码风丑请轻喷)

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define ll long long
#define maxn 300000 
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    } 
    while(c<='9'&&c>='0')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void print(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>=10)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}
int n;
struct node
{
    int st,ed,num,id;
}s[maxn];
inline bool cmp(node a,node b)
{
    if(a.st==b.st) 
    {
        return a.ed<b.ed;
    }
    else return a.st<b.st;
}
inline bool Cmp(node a,node b)
{
    return a.id<b.id;
}
int main()
{
    n=read();
    for(rg int i=1;i<=n;++i)
    {
        s[i].st=read();
        s[i].ed=read();
        s[i].id=i;
    }
    sort(s+1,s+1+n,cmp);
    for(rg int i=1;i<=n;++i)
    {
        int ans=i;
        int l=i,r=n;
        if(s[i+1].st>s[i].ed) continue;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(s[mid].st<=s[i].ed)
            {
                ans=mid;
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        s[i].num+=(ans-i);
    }
    sort(s+1,s+1+n,Cmp);
    for(rg int i=1;i<=n;++i)
    {
        print(s[i].num);
        putchar('\n');
    }
}