差分做法(注意边界):
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; }