UVALive 6606 Meeting Room Arrangement

COJ有这题，一模一样的，COJ应该是从这个OJ上拿的吧。

按右端点排序，然后从第一个开始贪心的取相邻的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 40
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct abc
{
    int l,r;
    bool operator<(const abc &b)const
    {
        return r<b.r;
    }
}a[22];
int main()
{
    //freopen("1.txt","r",stdin);
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int i,j,l,r,sum=1;
        for(i=0;;i++)
        {
            scanf("%d%d",&l,&r);
            if(l==0&&r==0) break;
            a[i].l=l,a[i].r=r;
        }
        sort(a,a+i);
        l=a[0].r;
        for(j=1;j<i;j++)
            if(a[j].l>=l) sum++,l=a[j].r;
        printf("%d\n",sum);
    }
    return 0;
}

思路：RMQ+二分

把递推和用RMQ先预处理一下区间最大值，然后枚举下标 i，然后二分查找 i 后面>=x位置的最小值，其差就是区间。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 500050
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll a[maxn],dp[maxn][34];
void RMQ(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
        dp[i][0]=a[i];
    for(j=1;(1<<j)<=n;j++)
        for(i=1;i+(1<<j)-1<=n;i++)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
ll rmq(int l,int r)
{
    int k=log2(r-l+1.0);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main()
{
    //freopen("1.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,x,i,ans;
        scanf("%d%d",&n,&x);
        for(i=1;i<=n;i++)
            scanf("%lld",a+i),a[i]=a[i]+a[i-1];
        RMQ(n);
        for(i=0,ans=INF;i<n;i++)
        {
            int l=i+1,r=n,mid;
            while(l<r)
            {
                mid=(l+r)>>1;
                if(rmq(i+1,mid)-a[i]>=x) r=mid;
                else l=mid+1;
            }
            if(a[r]-a[i]>=x) ans=min(ans,r-i);
        }
        if(ans==INF) puts("-1");
        else printf("%d\n",ans);
    }
    return 0;
}