社区讨论

65分TLE求助

P7913[CSP-S 2021] 廊桥分配参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo13r27i
此快照首次捕获于
2023/10/22 14:43
2 年前
此快照最后确认于
2023/11/02 14:14
2 年前
查看原帖
rt,大体思路是用数组s1is_{1i}存给国内机场i个廊桥时,有多少飞机可以停在廊桥上,用前缀和和链表实现。
两次排序O(m1logm1+m2logm2m_1log_{m_1} + m_2log_{m_2})
分配廊桥时为O(m1+n+m2+nm_1+n+m_2+n)
计算答案时为O(n)
总复杂度为O(m1logm1+m2logm2+nm_1log_{m_1} + m_2log_{m_2}+n)
蒟蒻分析复杂度不知对不对
CPP
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
using namespace std;
const int N=1e5+10;

struct Node{
	int l,r;
	int next;
	bool operator<(const Node x)const{return l<x.l;}//排序用
}pl1[N],pl2[N];

int n,m1,m2,ans,s1[N],s2[N];


int main()
{
//	freopen("airport.in","r",stdin);
//	freopen("airport.out","w",stdout);
	cin>>n>>m1>>m2;
	for(int i=1,l,r;i<=m1;++i)
	{
		scanf("%d%d",&l,&r);
		pl1[i].l=l;pl1[i].r=r;
	}
	for(int i=1,l,r;i<=m2;++i)
	{
		scanf("%d%d",&l,&r);
		pl2[i].l=l;pl2[i].r=r;
	}
	sort(pl1+1,pl1+m1+1);for(int i=1;i<=m1;++i){pl1[i].next=(i+1)%(m1+1);}//链表指向初始化
	sort(pl2+1,pl2+m2+1);for(int i=1;i<=m2;++i){pl2[i].next=(i+1)%(m2+1);}
	pl1[0].next=1;pl2[0].next=1;//每次分配的飞机起点用pl[0].next指向
	for(int i=1;i<=n;++i)
	{
		int ti=0,to=0;//to存修改指向的点,ti存删除的点中飞机的飞离时间
		for(int j=pl1[0].next;j!=0;j=pl1[j].next)
		{
			if(ti>pl1[j].l)
			{
				to=j;
				continue;
			}
			pl1[to].next=pl1[j].next;//链表删点
			ti=pl1[j].r;
			s1[i]++;
		}
		s1[i]+=s1[i-1];//前缀和
	}
	for(int i=1;i<=n;++i)//同上
	{
		int ti=0,to=0;
		for(int j=pl2[0].next;j!=0;j=pl2[j].next)
		{
			if(ti>pl2[j].l)
			{
				to=j;
				continue;
			}
			pl2[to].next=pl2[j].next;
			ti=pl2[j].r;
			s2[i]++;
		}
		s2[i]+=s2[i-1];
	}
	for(int i=0;i<=n;++i)ans=max(ans,s1[i]+s2[n-i]);//计算答案
	printf("%d\n",ans);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...