题解：B4319 [语言月赛 202504] 礼堂预约

本题考察日期计算和简单排序算法，对选手的阅读能力、分析能力、代码能力都有比较高的要求。如果选手没有采用合适的写法，可能会导致代码量增大。

首先，我们需要一个函数，计算当前日期，对应的第二天日期。因为这个过程涉及到数字加法，所以我推荐使用 int 存储，这样八位数

dt

对应的年、月、日就分别是 y=dt%10000,m=dt/100%100,d=dt%100。

为了计算

y

年

m

月的天数

maxd

，我们可以用一个数组记录平年

12

个月的天数；然后如果是闰年

2

月，再额外加一天即可。

算好上述变量后，第二天可以按照如下流程计算：

通常情况下， $y$ 年 $m$ 月 $d$ 日的第二天是 $y$ 年 $m$ 月 $d+1$ 日。
但如果 $d+1>maxd$ ，那么答案是 $y$ 年 $m+1$ 月 $1$ 日。
如果此时 $m+1$ 是 $13$ ，那么就要变成 $y+1$ 年 $1$ 月。

该部分的代码如下：

CPP

int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int tomorrow(int dt){
	int y=dt/10000,m=dt/100%100,d=dt%100;
	int maxd=days[m];
	if(m==2 && (y%4==0 && y%100!=0 || y%400==0))
		maxd=29;
	d++;
	if(d>maxd){
		d=1;
		m++;
	}
	if(m==13){
		m=1;
		y++;
	}
	return y*10000+m*100+d;
}

下一步我们考虑日程表的维护。预约在早上的活动最后一定在早上，下午、晚上类似，因此早上、下午、晚上是平行而独立的三个日程表，直接加一维数组，

0

表示早上，

1

表示下午，

2

表示晚上即可。

为了更方便地比较活动类型的优先程度，可以规定 O,C,P 分别对应数字

0,1,2

，这样，发生冲突时，类型更大的活动时间会被修改。

为了更方便地查找冲突的活动，我们可以规定日程表里所有活动按照举办时间的先后排序。具体地，

act(tme,i)

表示

tme

时间（

0,1,2

之一）、第

i

个举办的活动编号，而

cact(tme)

表示时间

tme

的活动个数。

CPP

int n,date[5005];
int type[5005];//0=O, 1=C, 2=P
int act[3][5005],cact[3];// 0=M, 1=A, 2=E
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s>>date[i];
		
		if(s[0]=='O')type[i]=0;
		else if(s[0]=='C')type[i]=1;
		else type[i]=2;
		
		cin>>s;
		int tme;
		if(s[0]=='M')tme=0;
		else if(s[0]=='A')tme=1;
		else tme=2;
        
        //插入新活动部分的代码，具体实现在下文提到
    }
	for(int i=1;i<=n;i++)
		printf("%d\n",date[i]);
	return 0;
}

每次加入新活动时，使用类似插入排序的做法就可以保持数组的有序，具体地，假设要把编号 to_arr 的活动插入日程表，那么用一重循环

j

从

1

枚举到

cact(tme)

：

如果 $date_i > date_{act(tme,j)}$ ，表示 $i$ 的插入点在第 $j$ 个活动之后，不需要处理。
如果 $date_i<date_{act(tme,j)}$ ，那么 $i$ 应该插入在第 $j$ 个活动之前，换言之 $i$ 成为了第 $j$ 个活动，而原来第 $j$ 个活动成了需要插入的活动，代码中体现为 swap(act[tme][j],to_arr)。
如果二者相等，那么发生了一次冲突。此时比较二者谁的“权力”更大，如果 $i$ 的“权力“更大，就把 $act(tme,j)$ 这个活动**从日程中拉出来（变成需要插入的活动）**天数 $+1$ ，然后自己进去；否则自己天数 $+1$ 。

最后肯定剩下一个尚未插入的活动，直接安排到末尾即可。

CPP

		int to_arr=i;
		for(int j=1;j<=cact[tme];j++){
			int target=act[tme][j];//尝试把 to_arr 插入 target 所在位置
			if(date[target]==date[to_arr]){//活动撞了
				if(type[target]>type[to_arr] || type[target]==type[to_arr] && target>to_arr){
					//to_arr 权力更大，从 target 位置拉下来
					swap(act[tme][j],to_arr);
				}
				date[to_arr]=tomorrow(date[to_arr]);
			}
			else if(date[target]>date[to_arr])//正常插入排序
				swap(act[tme][j],to_arr);
		}
		cact[tme]++;
		act[tme][cact[tme]]=to_arr;

题解：B4319 [语言月赛 202504] 礼堂预约

文章操作

相关推荐

评论

题解：B4319 [语言月赛 202504] 礼堂预约