首页 > 代码库 > HDU 4553 约会安排(二维线段树）

HDU 4553 约会安排(二维线段树）

2024-11-08 07:23:40   203人阅读

Problem Description
　　寒假来了，又到了小明和女神们约会的季节。
　　小明虽为屌丝级码农，但非常活跃，女神们常常在小明网上的大段发言后热情回复“呵呵”，所以，小明的最爱就是和女神们约会。与此同时，也有很多基友找他开黑，由于数量实在过于巨大，怎么安排时间便成了小明的一大心事。
　　我们已知小明一共有T的空闲时间，期间会有很多女神或者基友来找小明。
　　作为一个操作系统曾经怒考71分的大神，小明想到了一个算法，即“首次适应算法”，根据操作系统课本的描述，就是找一段最靠前的符合要求的连续空间分配给每个请求，由此小明做出了一个决定：
　　当一个基友来找小明时，小明就根据“首次适应算法”来找一段空闲的时间来和基友约好，如果找到，就说“X,let’s fly”（此处，X为开始时间），否则就说“fly with yourself”；
　　当女神来找小明时，先使用一次“首次适应算法”，如果没有找到，小明就冒着木叽叽的风险无视所有屌丝基友的约定，再次使用“无视基友首次适应算法”，两次只要有一次找到，就说“X,don’t put my gezi”（此处，X为开始时间），否则就说“wait for me”
　　当然，我们知道小明不是一个节操负无穷的人，如果和女神约会完，还有剩余时间，他还是会和原来约好的基友去dota的。（举个例子：小西（屌丝）和小明约好在1~5这个时间单位段内打dota，这时候，女神来和小明预约长度为3的时间段，那么最终就是1~3小明去和女神约会，搞定后在4~5和小西打dota）
　　小明偶尔也会想要学习新知识，此时小明就会把某一个时间区间的所有已经预定的时间全部清空用来学习并且怒吼“I am the hope of chinese chengxuyuan!!”，不过小明一般都是三分钟热度，再有人来预定的话，小明就会按耐不住寂寞把学习新知识的时间分配出去。
 

Input
输入第一行为CASE，表示有CASE组测试数据；
每组数据以两个整数T，N开始，T代表总共的时间，N表示预约请求的个数；
接着的N行，每行表示一个女神或者基友的预约，“NS QT”代表一个女神来找小明约一段长为QT的时间，“DS QT”则代表一个屌丝的长为QT的请求，当然也有可能是小明想学知识了，“STUDY!! L R”代表清空L~R区间内的所有请求。

[Technical Specification]
1. 1 <= CASE <= 30
2. 1 <= T, N <= 100000
3. 1 <= QT <= 110000
4. 1 <= L <= R <=T
 

Output
对于每一个case，第一行先输出“Case C:”代表是第几个case，然后N行，每行对应一个请求的结果(参照描述)。
输出样本(可复制此处)：
“X,let‘s fly”,”fly with yourself”,”X,don‘t put my gezi”,”wait for me”,”I am the hope of chinese chengxuyuan!!”
 

Sample Input
1
5 6
DS 3
NS 2
NS 4
STUDY!! 1 5
DS 4
NS 2
 

Sample Output
Case 1:
1,let‘s fly
4,don‘t put my gezi
wait for me
I am the hope of chinese chengxuyuan!!
1,let‘s fly
1,don‘t put my gezi
 
题意：中文。
线段树做法：二维，一维表示屌丝，一维表示女神。通过题意我们知道女神对于
屌丝来说有绝对优势，所以对于屌丝的更新来说只需要考虑自己的第一维，而对
于女神来说更新的时候先在屌丝没用的时间里找，如果没找到就要占用屌丝的时间了。
也就是说无论女神在哪占用的时间，女神和屌丝相应的时间段都要更新，
这道题由于要找端点，所以要区间合并。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int maxn=100000+10;
int sum[2][maxn<<2],col[2][maxn<<2];//sum[2][i]屌丝和女神,col=1表示有空位
int lsum[2][maxn<<2],rsum[2][maxn<<2];
int t,n,m;
void pushup(int p,int rs,int s)
{
    lsum[p][rs]=lsum[p][rs<<1];
    rsum[p][rs]=rsum[p][rs<<1|1];
    if(lsum[p][rs<<1]==(s-(s>>1)))  lsum[p][rs]+=lsum[p][rs<<1|1];
    if(rsum[p][rs<<1|1]==(s>>1))  rsum[p][rs]+=rsum[p][rs<<1];
    sum[p][rs]=max(max(sum[p][rs<<1],sum[p][rs<<1|1]),rsum[p][rs<<1]+lsum[p][rs<<1|1]);
}
void pushdown(int p,int rs,int s)
{
    if(col[p][rs]!=-1)
    {
        if(col[p][rs]==1)
        {
            sum[p][rs<<1]=lsum[p][rs<<1]=rsum[p][rs<<1]=(s-(s>>1));
            sum[p][rs<<1|1]=lsum[p][rs<<1|1]=rsum[p][rs<<1|1]=(s>>1);
            col[p][rs<<1]=col[p][rs<<1|1]=1;
            col[p][rs]=-1;
        }
        else
        {
            sum[p][rs<<1]=lsum[p][rs<<1]=rsum[p][rs<<1]=0;
            sum[p][rs<<1|1]=lsum[p][rs<<1|1]=rsum[p][rs<<1|1]=0;
            col[p][rs<<1]=col[p][rs<<1|1]=0;
            col[p][rs]=-1;
        }
    }
}
void build(int p,int l,int r,int rs)
{
    col[p][rs]=-1;
    sum[p][rs]=lsum[p][rs]=rsum[p][rs]=r-l+1;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    build(p,l,mid,rs<<1);
    build(p,mid+1,r,rs<<1|1);
}
void update(int p,int x,int y,int c,int l,int r,int rs)
{
    if(l>=x&&r<=y)
    {
        col[p][rs]=c;
        if(c) sum[p][rs]=lsum[p][rs]=rsum[p][rs]=r-l+1;
        else  sum[p][rs]=lsum[p][rs]=rsum[p][rs]=0;
        return ;
    }
    pushdown(p,rs,r-l+1);
    int mid=(l+r)>>1;
    if(x<=mid)  update(p,x,y,c,l,mid,rs<<1);
    if(y>mid)  update(p,x,y,c,mid+1,r,rs<<1|1);
    pushup(p,rs,r-l+1);
}
int query(int p,int x,int l,int r,int rs)
{
    if(l==r)
        return l;
    pushdown(p,rs,r-l+1);
    int mid=(l+r)>>1;
    if(sum[p][rs<<1]>=x)  return query(p,x,l,mid,rs<<1);
    else if(rsum[p][rs<<1]+lsum[p][rs<<1|1]>=x)  return mid-rsum[p][rs<<1]+1;
    else  return query(p,x,mid+1,r,rs<<1|1);
    pushup(p,rs,r-l+1);
}

int main()
{
    int x,l,r,ans;
    int cas=1;
    char str[15];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        build(0,1,n,1);
        build(1,1,n,1);
        printf("Case %d:\n",cas++);
        while(m--)
        {
            scanf("%s",str);
            if(str[0]=='D')
            {
                scanf("%d",&x);
                if(sum[0][1]<x)
                    puts("fly with yourself");
                else
                {
                    ans=query(0,x,1,n,1);
                    printf("%d,let's fly\n",ans);
                    update(0,ans,ans+x-1,0,1,n,1);
                }
            }
            else if(str[0]=='N')
            {
                scanf("%d",&x);
                if(sum[0][1]>=x)
                {
                    ans=query(0,x,1,n,1);
                    printf("%d,don't put my gezi\n",ans);
                    update(0,ans,ans+x-1,0,1,n,1);
                    update(1,ans,ans+x-1,0,1,n,1);
                }
                else
                {
                    if(sum[1][1]>=x)
                    {
                        ans=query(1,x,1,n,1);
                        printf("%d,don't put my gezi\n",ans);
                        update(0,ans,ans+x-1,0,1,n,1);
                        update(1,ans,ans+x-1,0,1,n,1);
                    }
                    else
                        puts("wait for me");
                }
            }
            else
            {
                scanf("%d%d",&l,&r);
                puts("I am the hope of chinese chengxuyuan!!");
                update(0,l,r,1,1,n,1);
                update(1,l,r,1,1,n,1);
            }
        }
    }
    return 0;
}


HDU 4553 约会安排(二维线段树）


联系
我们