【洛谷2439】【SDOI2005】阶梯教室设备利用

阶梯教室设备利用"/>

【洛谷2439】【SDOI2005】阶梯教室设备利用

题目背景

我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定，如果两个演讲时间有部分或全部重复，那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室，也就是说，我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。

题目描述

请写一个程序：

读入所有演讲的起始和终止时间；

计算最大的可能演讲总时间；

输入输出格式

输入格式：

第一行包括一个正整数n，n<=10000，为所有的演讲的数目。以下的n行每行含有两个由空格隔开的整数p和k，0<=p< k<=30000。这样的一对整数表示一个演讲由时间p开始到时间k结束。
UPD1:
n<=100000,0<=p< k<=30000

输出格式：

输出唯一的一个整数，为最长的演讲总时间。

输入输出样例

输入样例#1：

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

输出样例#1：

16

题解

50分解法：

贪心+dp
首先贪心排序每个演讲的结束时间，再依次转移。
dp方程：
f[a[i].ed]=max(f[a[i].ed],f[j]+a[i].ed-a[i].st)(0<=j<=a[i].st)
a[i].st表示每个演讲开始时间；a[i].ed表示结束时间。

80分解法：

由于pk的范围变大，普通dp思路已不能解决问题，这时我们需要把pk离散化一下即可得到80分。

100分解法：

由于n到了10^5级别，所以我们可以在dp内部进行优化，通过二分查找一个当前最优的演讲，然后转移这个演讲（这样也省下了离散化）

My Code

其实这道题是莒县一中模拟赛的题，但是题目标题和描述换了，数据却一样(雾)

50分解法

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct t{int st,ed;
}a[10005];
int n,ans,f[30005];
int cmp(t a,t b){return a.ed<b.ed;
}
int main(){freopen("rez.in","r",stdin);freopen("rez.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].st,&a[i].ed);}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){for(int j=a[i].st;j>=0;j--){f[a[i].ed]=max(f[a[i].ed],f[j]+a[i].ed-a[i].st);}}int ans=0;for(int i=1;i<=30001;i++){if(ans<=f[i])ans=f[i];}printf("%d",ans);return 0;
}

80分解法：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
struct t{int st,ed;
}a[100005];
int n,ans,f[200005],aa[200005];
map<int,int>mp;
int cmp(t a,t b){return a.ed<b.ed;
}
int main(){freopen("rez.in","r",stdin);freopen("rez.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].st,&a[i].ed);aa[i*2-2]=a[i].st;aa[i*2-1]=a[i].ed;}sort(aa,aa+2*n);for(int i=0;i<=2*n-1;i++){mp[aa[i]]=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){int st=a[i].st,ed=a[i].ed;for(int j=mp[st];j>=0;j--){f[mp[ed]]=max(f[mp[ed]],f[j]+ed-st);}}int ans=0;for(int i=1;i<=200001;i++){if(ans<=f[i])ans=f[i];}printf("%d",ans);return 0;
}

100分解法：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct t{int st,ed;
}a[100005];
int n,ans,f[100005];
int cmp(t a,t b){return a.ed<b.ed;
}
int main(){freopen("rez.in","r",stdin);freopen("rez.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].st,&a[i].ed);}sort(a+1,a+n+1,cmp);for (int i=1;i<=n;i++){f[i]=f[i-1]; int l=0,r=i-1;while(l<r){int m=(l+r+1) >> 1;if (a[m].ed>a[i].st)r=m-1; else l=m;}if (f[l]+a[i].ed-a[i].st>f[i])f[i]=f[l]+a[i].ed-a[i].st;}  printf("%d",f[n]);return 0;
}