自动搬运

查看原文

来自洛谷，原作者为

	樱雪喵 无尽欺骗，无限祈愿 | AFOed | qq: 3480681868

搬运于2025-08-24 21:31:00，当前版本为作者最后更新于2022-09-21 01:12:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此题现有题解较为冗长，因此前来贡献一发（目前的）最短解。

首先正常的思路是直接按题意模拟。即：

• 枚举当前时刻 $t$
• 对于每个人，标记该时刻想要拿到的书
• 根据题目的要求判断冲突情况
• 对书进行分配

实现起来复杂的地方主要在处理冲突上，考虑从这方面简化代码。

我们知道，时刻为 $t$ 时第 $i$ 个人已经等待的时间与他即将读哪本书无关，只与这个人开始等待的时刻有关。

故设 $last_i$ 为第 $i$ 个人开始等待（即读完上一本书）的时刻。则把人按照 $last$ 的值为第一关键字，到达时间的值为第二关键字进行升序排列，不难证明对于同一本书，等待时间更长的人一定先被计算到。

既然已经说到这步，我们直接按把人排序后的先后顺序分配书就可以避免冲突问题了。

时间上可能比其他做法多了个排序的 $\log$，但对于此题数据范围依然绰绰有余。

AC code:

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int T,n;
struct node{
	int arr,k,ls; 
	int s[10],t[10],flg[10];
}a[N];
bool cmp(node x,node y){
	if(x.ls==y.ls) return x.arr<y.arr;
	else return x.ls<y.ls;
}
int ans,bk[N];
int main()
{
	scanf("%d%d",&T,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].arr,&a[i].k);a[i].arr++;
		for(int j=1;j<=a[i].k;j++) scanf("%d%d",&a[i].s[j],&a[i].t[j]);
		a[i].ls=a[i].arr;
	}
	for(int t=1;t<=T;t++)
	{
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++)
		{
			if(a[i].ls>t||a[i].arr>t) continue; 
			for(int k=1;k<=a[i].k;k++)
			{
				if((bk[a[i].s[k]]<=t)&&(!a[i].flg[k]))
				{
					ans++;a[i].flg[k]=1;
					a[i].ls=bk[a[i].s[k]]=t+a[i].t[k];
					break;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

既然都看到这了，就给 yx 点个赞吧 qwq