自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 21:18:37，当前版本为作者最后更新于2025-04-13 18:18:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先，我们需要一个函数，计算当前日期，对应的第二天日期。因为这个过程涉及到数字加法，所以我推荐使用 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$ 月。

该部分的代码如下：

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$ 的活动个数。

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$。

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

		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;