原代码:
#include<bits/stdc++.h>
using namespace std;
struct unit
{
int bg,ed;
}fire[20005]={0};
int main()
{
int n;
scanf("%d",&n);
int disc1[20005]={0};
for(int i=1;i<=n;i++)
{
scanf("%d%d",&fire[i].bg,&fire[i].ed);
disc1[2*i-1]=fire[i].bg;
disc1[2*i]=fire[i].ed;
}
sort(disc1+1,disc1+1+2*n);//排序以便离散化
int it=2,nlen=1;
while(it<=2*n) disc1[it]==disc1[nlen]?it++:disc1[++nlen]=disc1[it++];//离散化
int disc2[20005]={0};
for(int i=1;i<=n;i++)
{
disc2[lower_bound(disc1+1,disc1+1+nlen,fire[i].bg)-disc1]++;
disc2[lower_bound(disc1+1,disc1+1+nlen,fire[i].ed)-disc1]--;
}
// for(int i=1;i<=nlen;i++)printf("%d:%d ",disc1[i],disc2[i]);
int sum[20005]={0};
int ans=0;
for(int i=1;i<=nlen;i++)
{
sum[i]=sum[i-1]+disc2[i];
if(sum[i-1])ans+=disc1[i]-disc1[i-1];
}
printf("%d",ans);
return 0;
}
修改后的代码:
#include<bits/stdc++.h>
using namespace std;
struct unit
{
int bg,ed;
}fire[40005]={0};
int main()
{
int n;
scanf("%d",&n);
int disc1[40005]={0};
for(int i=1;i<=n;i++)
{
scanf("%d%d",&fire[i].bg,&fire[i].ed);
disc1[2*i-1]=fire[i].bg;
disc1[2*i]=fire[i].ed;
}
sort(disc1+1,disc1+1+2*n);//排序以便离散化
int it=2,nlen=1;
while(it<=2*n) disc1[it]==disc1[nlen]?it++:disc1[++nlen]=disc1[it++];//离散化
int disc2[40005]={0};
for(int i=1;i<=n;i++)
{
disc2[lower_bound(disc1+1,disc1+1+nlen,fire[i].bg)-disc1]++;
disc2[lower_bound(disc1+1,disc1+1+nlen,fire[i].ed)-disc1]--;
}
// for(int i=1;i<=nlen;i++)printf("%d:%d ",disc1[i],disc2[i]);
int sum[40005]={0};
int ans=0;
for(int i=1;i<=nlen;i++)
{
sum[i]=sum[i-1]+disc2[i];
if(sum[i-1])ans+=disc1[i]-disc1[i-1];
}
printf("%d",ans);
return 0;
}
只改了个数组大小,蒟蒻求助!!