P2352 队爷的新书 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意大概是给n个区间，如果某个数属于若干区间的话，这些区间的这个数的和最大是多少。
毫无疑问，贪心来看这个数必然是某个区间的右端点。
那么接下来很容易想到按照右端点排一下序，来计算相应的和。
但n是1e5级别的，n^2会超时。
按照右端点排序有个很好的性质，那就是对于排序后第i个区间，前i-1个区间的左端点必然是小于等于它的。我们不妨排序左端点，找到左端点中共有多少数小于等于右端点，这些数当中包含右端点在i左边的i-1个区间，剩下的就是右端点在i右边或者重合的，换言之，就是右端点i被这些区间包含。
由于左端点也是有序的，我们可以用二分来做
查看代码
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
int n;
signed main()
{
cin>>n;
vector<int>a(n),b(n);
for(int i=0;i<n;i++)cin>>a[i]>>b[i];
sort(a.begin(),a.end());
sort(b.begin(),b.end());
int ans=0;
for(int i=0;i<n;i++)
{
int l=0,r=n-1;
while(l<r)
{
int mid=l+r+1>>1;
if(a[mid]<=b[i])l=mid;
else r=mid-1;
}
ans=max(ans,(l-i+1)*b[i]);
}
cout<<ans;
return 0;
}标签：队爷,P2352,int,新书,端点,区间,include From： https://www.cnblogs.com/qbning/p/17585331.html