考试时的40分代码:
#include<bits/stdc++.h>
using namespace std;
const int mm=100005;
int ne[mm],wa[mm],lq[mm];
int n,my1,my2,ans;
struct node{
int s=0;
int e=0;
}m1[mm],m2[mm];
bool cmp(node x,node y)
{
return x.s<y.s;
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch-'0'); ch=getchar();}
return x*f;
}
int main()
{
n=read();my1=read();my2=read();
for(int i=1;i<=my1;i++)
{
m1[i].s=read();
m1[i].e=read();
}
sort(m1+1,m1+my1+1,cmp);
for(int i=1;i<=my1;i++)
{
for(int j=1;j<=n;j++)
{
if(lq[j]<=m1[i].s)
{
lq[j]=m1[i].e;
ne[j]++;
break;
}
}
}
memset(lq,0,sizeof(lq));
for(int i=1;i<=my2;i++)
{
m2[i].s=read();
m2[i].e=read();
}
sort(m2+1,m2+my2+1,cmp);
for(int i=1;i<=my2;i++)
{
for(int j=1;j<=n;j++)
{
if(lq[j]<=m2[i].s)
{
lq[j]=m2[i].e;
wa[j]++;
break;
}
}
}
for(int i=n;i>=1;i--)
{
int xx=0;
for(int j=0;j<=i;j++) xx+=ne[j];
for(int j=0;j<=n-i;j++) xx+=wa[j];
ans=max(ans,xx);
}
cout<<ans;
return 0;
return 0;
}
估计神犇们都笑抽筋了吧
脑子清醒后优化的100分代码:
#include<bits/stdc++.h>
using namespace std;
const int mm=100005;
int ne[mm],wa[mm],lq[mm];
int n,my1,my2,ans;
struct node{
int s=0;
int e=0;
}m1[mm],m2[mm];
bool cmp(node x,node y)
{
return x.s<y.s;
}
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') {ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();}
return x;
}
int main()
{
n=read(),my1=read(),my2=read();
for(register int i(1);i<=my1;i++)
{
m1[i].s=read(),m1[i].e=read();
}
sort(m1+1,m1+my1+1,cmp);
for(register int i(1);i<=my1;i++)
{
for(register int j(1);j<=n;j++)
{
if(lq[j]<=m1[i].s)
{
lq[j]=m1[i].e;
ne[j]++;
break;
}
}
}
memset(lq,0,sizeof(lq));
for(register int i=1;i<=my2;i++)
{
m2[i].s=read(),m2[i].e=read();
}
sort(m2+1,m2+my2+1,cmp);
for(register int i=1;i<=my2;i++)
{
for(register int j=1;j<=n;j++)
{
if(lq[j]<=m2[i].s)
{
lq[j]=m2[i].e;
wa[j]++;
break;
}
}
}
int xx=0;
for(register int i=1;i<=n;++i) xx+=ne[i];
ans=xx;
for(register int i=n;i>=1;i--)
{
xx-=ne[i];
xx+=wa[n-i+1];
ans=max(ans,xx);
}
cout<<ans;
return 0;
}