社区讨论
65分TLE求助
P7913[CSP-S 2021] 廊桥分配参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo13r27i
- 此快照首次捕获于
- 2023/10/22 14:43 2 年前
- 此快照最后确认于
- 2023/11/02 14:14 2 年前
rt,大体思路是用数组存给国内机场i个廊桥时,有多少飞机可以停在廊桥上,用前缀和和链表实现。
两次排序O()
分配廊桥时为O()
计算答案时为O(n)
总复杂度为O()
#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 条回复,欢迎继续交流。
正在加载回复...