【HDU4553】【2棵线段树】【优先级同步互斥】

本文主要是介绍【HDU4553】【2棵线段树】【优先级同步互斥】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

约会安排

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 700 Accepted Submission(s): 202

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

Source

2013金山西山居创意游戏程序挑战赛——初赛（3）

Recommend

liuyiding

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mp push_back
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1const int MAXN = 100010;
int sum[2][MAXN*6],lsum[2][MAXN*6],rsum[2][MAXN*6];
int col[2][MAXN*6];int Case,n,m;
char str[10];void PushDown(int p,int rt,int l1,int l2)
{if(col[p][rt] != -1){sum[p][rt<<1] = lsum[p][rt<<1] = rsum[p][rt<<1] = l1 * col[p][rt];col[p][rt<<1] = col[p][rt];sum[p][rt<<1|1] = lsum[p][rt<<1|1] = rsum[p][rt<<1|1] = l2 * col[p][rt];col[p][rt<<1|1] = col[p][rt];col[p][rt] = -1;}
}void PushUp(int p,int l,int r,int rt)
{int m = (l + r) >> 1;lsum[p][rt] = lsum[p][rt<<1];rsum[p][rt] = rsum[p][rt<<1|1];if(lsum[p][rt<<1] == m - l) lsum[p][rt] += lsum[p][rt<<1|1];if(rsum[p][rt<<1|1] == r - m) rsum[p][rt] += rsum[p][rt<<1];sum[p][rt] = max(lsum[p][rt],rsum[p][rt]);sum[p][rt] = max(sum[p][rt],rsum[p][rt<<1]+lsum[p][rt<<1|1]);sum[p][rt] = max(sum[p][rt],max(sum[p][rt<<1],sum[p][rt<<1|1]));
}void build(int p,int l,int r,int rt)
{col[p][rt] = -1;sum[p][rt] = lsum[p][rt] = rsum[p][rt] = r - l ;if(r - l == 1){return ;}int m = (l + r) >> 1;build(p,lson);build(p,rson);
}
int query(int p,int range,int l,int r,int rt)
{if(r - l == 1){return l;}int m = (l + r) >> 1;PushDown(p,rt,m-l,r-m);if(sum[p][rt<<1] >= range){return query(p,range,lson);}else if(rsum[p][rt<<1] + lsum[p][rt<<1|1] >= range){return m - rsum[p][rt<<1];}else {return query(p,range,rson);}PushUp(p,l,r,rt);
}void update(int p,int L,int R,int c,int l,int r,int rt)
{if(L <= l && r <= R){col[p][rt] = c;sum[p][rt] = lsum[p][rt] = rsum[p][rt] = (r - l) * c;return ;}int m = (l + r) >> 1;PushDown(p,rt,m-l,r-m);if(L < m) update(p,L,min(R,m),c,lson);if(m < R) update(p,max(L,m),R,c,rson);PushUp(p,l,r,rt);
}int main()
{freopen("in.txt","r",stdin);scanf("%d",&Case);int C = 1;while(Case --){printf("Case %d:\n",C++);scanf("%d%d",&n,&m);build(0,1,n+1,1);build(1,1,n+1,1);// memset(sum,0,sizeof(sum));// memset(lsum,0,sizeof(lsum));// memset(rsum,0,sizeof(rsum));// memset(col,-1,sizeof(col));for(int i=0;i<m;i++){scanf("%s",str);if(str[0] == 'D'){int len;scanf("%d",&len);if(sum[0][1] < len){printf("fly with yourself\n");}else{int beg = query(0,len,1,n+1,1);printf("%d,let's fly\n",beg);update(0,beg,beg+len,0,1,n+1,1);}}else if(str[0] == 'N'){int len;scanf("%d",&len);if(sum[0][1] >= len){int beg = query(0,len,1,n+1,1);printf("%d,don't put my gezi\n",beg);update(1,beg,beg+len,0,1,n+1,1);update(0,beg,beg+len,0,1,n+1,1);}else{if(sum[1][1] >= len){int beg = query(1,len,1,n+1,1);printf("%d,don't put my gezi\n",beg);update(1,beg,beg+len,0,1,n+1,1);update(0,beg,beg+len,0,1,n+1,1);}else{puts("wait for me"); }}}else{int l, r;scanf("%d%d",&l,&r);puts("I am the hope of chinese chengxuyuan!!"); update(0,l,r+1,1,1,n+1,1);update(1,l,r+1,1,1,n+1,1);}}}
}

这篇关于【HDU4553】【2棵线段树】【优先级同步互斥】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！