差分做法(注意边界):
int sum[MAXN];
int main()
{
int n;rd(n);
int mx=0;
for (int i = 0; i < n*2; ++i)
{
int x,y;rd(x),rd(y);
++sum[x];--sum[y];
mx=max(mx,max(x,y));
}
int ans=0;
int tmp=0;
for (int i = 1; i <= mx; ++i)
{
tmp+=sum[i];
if(tmp>=2) ++ans;
}
cout<<ans<<endl;
return 0;
} 排序做法:
用排序一开始WA了两发之后换了差分的思路。。但是后来想了想这个思路没问题,更新处不能直接使 i = j ,要继续从 i + 1 寻找
例:
std::vector<pii > v;
int main()
{
int n;rd(n);
for (int i = 0; i < n*2; ++i)
{
int x,y;rd(x),rd(y);
v.push_back(make_pair(x,y));
}
sort(v.begin(), v.end());
int ans=0;
for(int i=0;i<n*2;++i)//注意下次应从i+1继续寻找而不是i=j
{
int j=i+1;
while(j<n*2&&v[j].first<v[i].second)
{
ans+=max(min(v[i].second,v[j].second) - max(v[j].first,v[i].first),0);
++j;
}
}
cout<<ans<<endl;
return 0;
} 
京公网安备 11010502036488号