T1:
这次最大的失误就是误判T1不可做...
因为每架飞机只要有空闲的廊桥就可以就可以停靠,以此可以推出一个结论:当廊桥数量增加时,已经停靠的飞机的位置是不会发生变化的。我们可以用两个优先队列求出有无限多个廊桥时,每架飞机停靠的位置。只有停靠的位置小于等于当前廊桥数的飞机才能停下。用前缀和处理下,接着枚举给每个区分配的廊桥数,O(1)更新答案即可。
代码:
#include<bits/stdc++.h> using namespace std; int read() { int s=0,w=1; char ch=getchar(); while(ch < '0' || ch > '9') { if(ch == '-') w=-1; ch=getchar();} while(ch <= '9' && ch >= '0') s=s*10+ch-'0',ch=getchar(); return s*w; } const int N=1e5+5; int n,m1,m2; struct Flight{ int l,r; } nn[N],ww[N]; bool cmp(Flight x,Flight y) { return x.l < y.l; } int s1[N],s2[N],cnt,ans1[N],ans2[N],maxn; priority_queue< pair<int,int> > q1,q2; priority_queue<int> qq1,qq2; void init() { s1[1]=1; q1.push(make_pair(-nn[1].r,1)); cnt=1; ans1[1]=1; for(int i=2;i<=m1;i++) { while(q1.size() && -q1.top().first < nn[i].l) { int k=q1.top().second; q1.pop(); qq1.push(-s1[k]); } if(qq1.size()) { s1[i]=-qq1.top(); ans1[s1[i]]++; qq1.pop(); q1.push(make_pair(-nn[i].r,i)); } else { cnt++; s1[i]=cnt; ans1[s1[i]]++; q1.push(make_pair(-nn[i].r,i)); } } s2[1]=1; q2.push(make_pair(-ww[1].r,1)); cnt=1; ans2[1]=1; for(int i=2;i<=m2;i++) { while(q2.size() && -q2.top().first < ww[i].l) { int k=q2.top().second; q2.pop(); qq2.push(-s2[k]); } if(qq2.size()) { s2[i]=-qq2.top(); ans2[s2[i]]++; qq2.pop(); q2.push(make_pair(-ww[i].r,i)); } else { cnt++; s2[i]=cnt; ans2[s2[i]]++; q2.push(make_pair(-ww[i].r,i)); } } for(int i=2;i<=n;i++) { ans1[i]+=ans1[i-1]; ans2[i]+=ans2[i-1]; } } int main() { //freopen("airport3.in","r",stdin); //freopen("1.txt","w",stdout); n=read(); m1=read(); m2=read(); for(int i=1;i<=m1;i++) nn[i].l=read(),nn[i].r=read(); for(int i=1;i<=m2;i++) ww[i].l=read(),ww[i].r=read(); sort(nn+1,nn+m1+1,cmp); sort(ww+1,ww+m2+1,cmp); init(); maxn=-1; for(int i=0;i<=n;i++) maxn=max(ans1[i]+ans2[n-i],maxn); printf("%d\n",maxn); return 0; }
T2:
分类讨论区间DP。