题目描述：
有n个小朋友，他们商量在保证作业做完的前提下去玩。第i个小朋友的可以玩耍时间为Si~ Ti。这里Si~Ti
表示的是时间段，比如Si=2,Ti=4，那么意味着这位小朋友在时刻1不能玩，时刻2、3、4可以去玩，时刻4以后都不能出去玩。如果在某个时刻，在一起玩的小朋友个数不少K个，那么这一时刻就是幸福的。现在你要求出所有幸福的时刻长度。
输入
三行 第一行：n k （n个小朋友，一起玩的小朋友达到k个为幸福）
第二行：S1 S2 ... Sn
第三行：T1 T2 ... Tn
输出
一行：幸福时刻的长度
样例输入
4 3
1 2 2 4
5 2 4 6
样例输出
2
数据范围限制
50% n<=1000 1<=Si<=Ti<=1000
100% n<=100000 1<=Si<=Ti<=1000000000
提示
时刻 1 2 3 4 5 6
第一个小朋友玩耍时间：X X X X X
第二个小朋友玩耍时间： X
第三个小朋友玩耍时间： X X X
第四个小朋友玩耍时间： X X X
第2分钟和第4分钟一起玩耍的小朋友达到了3个所以是幸福的时刻，幸福时刻长度为2。
50分思路：
这题50分思路还是计较简单的， 直接用一个数组把所有时刻的人数存入，最后再判断，每个时刻如果大于k，那ans++。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,s[1000001],t[1000001],ans,bz[1000001];
int main()
{
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
cin>>t[i];
for(int i=1;i<=n;i++)
for(int j=s[i];j<=t[i];j++)
if(bz[j]==-1) continue;
else
{
bz[j]++;
if(bz[j]>=k) bz[j]=-1,ans++;
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
加了线段数优化的代码：
#include<bits/stdc++.h>
using namespace std;
int sum[10000005]={};
int n,k;
int main()
{
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[x]++;
}
int o=-1;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(x>o)o=x;
sum[x+1]--;
}
int cnt=0,s=0;
for(int i=0;i<=o;i++)
{
cnt+=sum[i];
if(cnt>=k)
s++;
}
printf("%d
",s);
return 0;
}
100分思路：
这是50分做法的改编，将一个个的时间，改成以变化为分隔的时间段，大大加速了时间。
把每次变化（也就是s和t数组）合在一起排序，加上标记，每次变化，人数就变化，当人数满足幸福是，加上这次变化到下次变化前这个时间段。
核心代码：
if(bj[i]==0) re++;
if(bj[i]==1) re--;
if(re>=k) ans+=a[i+1]-a[i]; //1<=i<=2*n
再加上快排，标记，我们就能开始打代码。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,a[200010],bj[200010],re,ans;
void qsort(int i,int j)
{
int l=i,r=j,mid=a[(i+j+1)/2];
while(i<=j)
{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
a[0]=a[i];
a[i]=a[j];
a[j]=a[0];
bj[0]=bj[i];
bj[i]=bj[j];
bj[j]=bj[0];
i++; j--;
}
}
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
int main(){
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
bj[i]=0;
}
for(int i=1;i<=n;i++){
scanf("%d",&a[n+i]);
a[n+i]+=1;
bj[n+i]=1;
}
qsort(1,2*n);
for(int i=1;i<=2*n;i++){
if(bj[i]==0) re++;
if(bj[i]==1) re--;
if(re>=k) ans+=a[i+1]-a[i];
}
printf("%d",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
写博不易，请发现问题的大佬提出。
代码保证正确，请留赞再走。