社区讨论
数据加强警告(doge)
P7913[CSP-S 2021] 廊桥分配参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lobgawm3
- 此快照首次捕获于
- 2023/10/29 20:32 2 年前
- 此快照最后确认于
- 2023/11/04 01:57 2 年前
我这n*m+mlogm+O(n)都能过?
CPP#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rg register
using namespace std;
int n,m1,m2,ans=-233,cnt;
int ho[100010],ab[100010],f[100010];
struct nod{
int a,b;
}x1[100010],x2[100010];
bool cmp(nod x,nod y){
return x.a<y.a;
}
int main()
{
cin>>n>>m1>>m2;
for(rg int i=1;i<=m1;i++) scanf("%d %d",&x1[i].a,&x1[i].b);
for(rg int i=1;i<=m2;i++) scanf("%d %d",&x2[i].a,&x2[i].b);
sort(x1+1,x1+1+m1,cmp); sort(x2+1,x2+1+m2,cmp);
cnt=1;
for(rg int i=1;i<=m2;i++)
{
rg int k;
for(k=1;k<=cnt;k++)
if(x2[i].a>=f[k])
{
f[k]=x2[i].b; ab[cnt]++; break;
}
if(k>cnt)
{
cnt++; ab[cnt]=ab[cnt-1]+1; f[cnt]=x2[i].b;
}
else
{
for(int rg j=k;j<=cnt-1;j++) ab[j]++;
}
}
cnt=1; memset(f,0,sizeof(f));
for(rg int i=1;i<=m1;i++)
{
rg int k;
for(k=1;k<=cnt;k++)
if(x1[i].a>=f[k])
{
f[k]=x1[i].b; ho[cnt]++; break;
}
if(k>cnt)
{
cnt++; ho[cnt]=ho[cnt-1]+1; f[cnt]=x1[i].b;
}
else
{
for(int rg j=k;j<=cnt-1;j++) ho[j]++;
}
}
if(cnt<n)
{
for(rg int i=cnt+1;i<=n;i++) ho[i]=ho[cnt];
}
for(rg int i=0;i<=n;i++)
{
int j=n-i;
ans=max(ans,ho[i]+ab[j]);
}
printf("%d\n",ans);
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...