P2439 阶梯教室设备利用 P1868 饥饿的奶牛 SSL 1212 大厅安排

奶牛 SSL 1212 大厅安排"/>

P2439 阶梯教室设备利用 P1868 饥饿的奶牛 SSL 1212 大厅安排

题目描述：

题目传送门

解题思路：

考虑动态规划结合贪心求解。

理解题目，我们可以把每个演讲的时间段视作一个区间，起始时间就是左端点 a a a，结束时间就是右端点 b b b ，那么问题就变成了将 n n n 个区间进行排列，两两区间不能相交，使符合要求的某些区间长度和最大。

遇到这种区间要求性的题目，大概率需要将区间进行排序。这里我们采用贪心思想，将区间按右端点排序，如果右端点相等，则按左端点排序。

设 f i f_i fi​ 表示有前 i i i 个区间时，最大的符合要求的区间和。
可知，前 i i i 个区间的最大和必定不会小于前 i − 1 i-1 i−1 个区间的最大和，因此 f i f_i fi​ 可以从 f i − 1 f_{i-1} fi−1​ 转移而来，若 f i = f i − 1 f_i=f_{i-1} fi​=fi−1​，则说明不选择第 i i i 个区间。
若我们考虑选择第 i i i 个区间，那么我们就需要枚举一个 f j f_j fj​ 最大的符合 t i m e i , 左 端 点 > = t i m e j , 右 端 点 time_{i,左端点}>=time_{j,右端点} timei,左端点​>=timej,右端点​ 的 j j j 作为分割点，表示选择第 j j j 个区间与第 i i i 个区间连接，显然连接后 f i = f j + t i m e i , b − t i m e i , a f_i=f_j+time_{i,b}-time_{i,a} fi​=fj​+timei,b​−timei,a​ 。
f i = m a x ( f i − 1 , f j + t i m e i , b − t i m e i , a ) f_i=max(f_{i-1},f_j+time_{i,b}-time_{i,a}) fi​=max(fi−1​,fj​+timei,b​−timei,a​)
时间复杂度为 O ( n 2 ) O(n^2) O(n2)

显然这个时间复杂度通过此题是足够的，但如果放在这里， n < = 1.5 ∗ 1 0 5 n<=1.5*10^5 n<=1.5∗105， O ( n 2 ) O(n^2) O(n2) 做法明显不行。

我们发现， f i f_i fi​ 的值必定不会比 f i − 1 f_{i-1} fi−1​ 小，也就是说 f f f 是单调递增的。显然由于我们将右端点排过序了，也就是说右端点也是单调递增的，并且根据 f i f_i fi​ 表示第 i i i 个区间的性质， f i f_i fi​ 是与右端点一一对应的，可以考虑用二分查找优化。

通过二分查找，用 O ( l o g n ) O(log_n) O(logn​) 的复杂度找到一个最大且 t i m e i , 左 端 点 > = t i m e j , 右 端 点 time_{i,左端点}>=time_{j,右端点} timei,左端点​>=timej,右端点​ 的 j j j，代替了枚举 O ( n ) O(n) O(n) 的复杂度，将程序优化到 O ( n l o g n ) O(n~log_n) O(n logn​) ，可以通过此题。

CODE：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int n,ans=0;
struct QWQ
{int a,b;
} t[150010];
int f[150010]={0};
bool cmp(QWQ a,QWQ b)
{return a.b<b.b;
}
int search(int l,int r,int val)
{int mid,ans=0;while(l<=r){mid=l+(r-l)/2;if(t[mid].b<val){l=mid+1;ans=mid;}else r=mid-1;}return ans;
}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>t[i].a>>t[i].b;sort(t+1,t+n+1,cmp);for(int i=1;i<=n;i++){f[i]=max(f[i-1],f[search(1,i-1,t[i].a)]+t[i].b-t[i].a);ans=max(ans,f[i]);}cout<<ans;return 0;
}