习题：小幸福（离散化）

旧城等待， 2021-12-15 00:41 279阅读 0赞

小幸福  
【题目描述】  
有 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  
【样例说明】  
时刻 1 2 3 4 5 6  
第一个小朋友玩耍时间: X X X X X  
第二个小朋友玩耍时间: X  
第三个小朋友玩耍时间: X X X  
第四个小朋友玩耍时间: X X X  
第 2 分钟和第 4 分钟一起玩耍的小朋友达到了 3 个所以是幸福的时刻，幸福时刻长 度为 2。  
【数据范围】  
50% n<=1000 1<=Si<=Ti<=1000  
100% n<=100000 1<=Si<=Ti<=1000000000

分析：

这道题有许多其他的版本，由于比较重要，所以发一下。

我们第一个会想到暴力算法，但很明显数据范围不允许，我们又会想到离散化和线段树，但一般离散化会超时，线段树会超空间，看了几个大牛的程序才得到思路。

方法一

先将点离散，然后运用二分查找确定每个小朋友玩耍起始终止时间在离散数组中的位置，分别用1和-1标记，然后用计数器从头加到尾，中途若计数器不小于k就统计该段长度，时间效率O(nlogn)。

代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

var
      s,t:array[0..100000]of longint;
      a,b,f:array[0..200000]of longint;
      n,i,m,k,u,ans:longint;
    procedure find(x,y:longint);
    var l,r,mid:longint;
    begin
     l:=1; r:=m;
      repeat
         mid:=(l+r) div 2;
         if x<=a[mid] then r:=mid else l:=mid+1;
      until l>=r;
      f[l]:=f[l]+y;
    end;
    procedure qsort(l,h:longint);
    var i,j,t,m:longint;
    begin i:=l; j:=h;
     m:=a[(i+j) div 2];
     repeat
    while a[i]<m do inc(i);
    while m<a[j] do dec(j);
    if i<=j then
      begin   t:=a[i]; a[i]:=a[j]; a[j]:=t;
    inc(i); dec(j);  end;  until i>j;
     if i<h then qsort(i,h); if j>l then qsort(l,j);  end;
    begin
      assign(input,'e.in');
    reset(input);
    assign(output,'e.out');
    rewrite(output);
      readln(n,k);
      for i:=1 to n do
       begin
        read(s[i]); m:=m+1; a[m]:=s[i];
       end;
      for i:=1 to n do
       begin
        read(t[i]); m:=m+1;t[i]:=t[i]+1; a[m]:=t[i];
       end;
      qsort(1,m);
      b[1]:=a[1]; ans:=1;
      for i:=2 to m do
       if a[i]<>a[i-1] then begin ans:=ans+1; b[ans]:=a[i]; end;
      a:=b; m:=ans; ans:=0;
      for i:=1 to n do
       begin
        find(s[i],1); find(t[i],-1);
       end;
      for i:=1 to m-1 do
       begin
         u:=u+f[i];
         if u>=k then ans:=ans+a[i+1]-a[i];
       end;
      u:=u+f[m];
      if u>=k then ans:=ans+1;
      writeln(ans);
      close(input); close(output);
    end.

方法二

读入同时进行标记，起始为1，终止为-1，快排后一边删重复点，一边将重复点标记累加到这个时间点上，然后也用计数器从头到尾地进行累加，然后统计，麻烦的有的点既有小朋友加入，又有小朋友离开不太好处理，加几个语句就行了，删重复点和累加都是O(n)，但快排要O(nlogn)，故时间效率是O(nlogn)。

代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

var
      a,b,c,f,g:array[0..200001]of longint;
      n,i,m,k,t,h,l,ans:longint;
    procedure qsort(l,h:longint);
    var i,j,t,m:longint;
    begin i:=l; j:=h;
     m:=a[(i+j) div 2];
     repeat
    while a[i]<m do inc(i);
    while m<a[j] do dec(j);
    if i<=j then
      begin   t:=a[i]; a[i]:=a[j]; a[j]:=t;  t:=b[i]; b[i]:=b[j]; b[j]:=t;
    inc(i); dec(j);  end;  until i>j;
     if i<h then qsort(i,h); if j>l then qsort(l,j);  end;
    begin
      assign(input,'e.in');
    reset(input);
    assign(output,'e.out');
    rewrite(output);
      readln(n,k);
      for i:=1 to n do
       begin
        read(a[i*2-1]); b[i*2-1]:=1; m:=m+1;
       end;
      for i:=1 to n do
       begin
        read(a[i*2]); b[i*2]:=-1; m:=m+1;
       end;
      qsort(1,m);
      if b[1]=1 then h:=1 else if b[1]=-1 then l:=1;
      for i:=2 to m+1 do
       begin
        if a[i]=a[i-1]  then
         begin
           if b[i]=1 then h:=h+1;
           if b[i]=-1 then l:=l+1;
         end
         else
          begin
            ans:=ans+1;
            c[ans]:=h; f[ans]:=h-l; g[ans]:=a[i-1]; h:=0;l:=0;
           if b[i]=1 then h:=h+1;
           if b[i]=-1 then l:=l+1;
         end;
        end;
     t:=0;
     m:=ans; ans:=0;
     for i:=1 to m do
      begin
       t:=t+f[i];
       if t>=k then ans:=ans+g[i+1]-g[i]; if (t<k)and(c[i]+t-f[i]>=k) then ans:=ans+1;
      end;
     writeln(ans);
     close(input); close(output);
    end.

方法三（超时的离散化）

一个超时的离散化，也贴一下做参考。

代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

program e;
    var
      f:array[0..100000,1..2]of longint;
      a,b,s,t:array[0..100000]of longint;
      n,i,m,j,x,y,k,ans:longint;
    function find(x:longint):longint;
    var l,r,mid:longint;
    begin
      l:=1; r:=m;
      repeat
         mid:=(l+r) div 2;
         if x<=a[mid] then r:=mid else l:=mid+1;
      until l>=r;
      exit(l);
    end;
    procedure qsort(l,h:longint);
    var i,j,t,m:longint;
    begin i:=l; j:=h;
     m:=a[(i+j) div 2];
     repeat
    while a[i]<m do inc(i);
    while m<a[j] do dec(j);
    if i<=j then
      begin   t:=a[i]; a[i]:=a[j]; a[j]:=t;
    inc(i); dec(j);  end;  until i>j;
     if i<h then qsort(i,h); if j>l then qsort(l,j);  end;
    begin
      assign(input,'e.in');
    reset(input);
    assign(output,'e.out');
    rewrite(output);
      readln(n,k);
      for i:=1 to n do
      begin read(s[i]); m:=m+1; a[m]:=s[i]; end;
      for i:=1 to n do
      begin read(t[i]); m:=m+1; a[m]:=t[i]; end;
      qsort(1,m);
      b[1]:=a[1]; ans:=1;
      for i:=2 to m do
       if a[i]>a[i-1] then begin ans:=ans+1; b[ans]:=a[i]; end;
      a:=b; m:=ans; ans:=0;
      for i:=1 to n do
       begin
         x:=find(s[i]);
         y:=find(t[i]);
         for j:=x to y-1 do
          begin inc(f[j,1]); inc(f[j,2]); end;
         inc(f[y,1]);
       end;
      for i:=1 to m do
       begin  if f[i,2]>=k then ans:=ans+a[i+1]-a[i]; if (f[i,2]<k)and(f[i,1]>=k) then ans:=ans+1;  end;
      writeln(ans);
      close(input); close(output);
    end.

方法四（线段树）

线段树做的，也做参考。

代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

program e;
    var
      a:array[0..10000000,1..3]of longint;
      s,t:array[0..100000]of longint;
      n,i,m,ans,k:longint;
    procedure make(p,l,r:longint);
    var mid:longint;
    begin
      a[p,1]:=l; a[p,2]:=r; a[p,3]:=0;
      if l+1<r then
       begin
         mid:=(l+r) div 2;
         make(p*2,l,mid); make(p*2+1,mid+1,r);
       end;
    end;
    procedure put(p,l,r:longint);
    var mid:longint;
    begin
      if (a[p,1]=a[p,2]) then begin a[p,3]:=a[p,3]+1; exit; end;
      mid:=(a[p,1]+a[p,2]) div 2;
      if r<=mid then put(p*2,l,r)
       else if l>mid then put(p*2+1,l,r)
        else
          begin
            put(p*2,l,mid); put(p*2+1,mid+1,r);
          end;
      a[p,3]:=a[p*2,3]+a[p*2+1,3];
    end;
    procedure get(p:longint);
    var mid:longint;
    begin
      if a[p,1]=a[p,2] then inc(ans,ord(a[p,3]>=k))
       else begin get(p*2); get(p*2+1); end;
    end;
    begin
      assign(input,'e.in');
    reset(input);
    assign(output,'e.out');
    rewrite(output);
      readln(n,k);
      for i:=1 to n do
       read(s[i]);
      for i:=1 to n do
      begin read(t[i]); if t[i]>m then m:=t[i]; end;
      make(1,1,m);
      for i:=1 to n do
       begin
         put(1,s[i],t[i]);
       end;
      get(1);
      writeln(ans);
      close(input); close(output);
    end.

转载于:https://www.cnblogs.com/qtyytq/p/4293488.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/b381db3fdd1a4c6692bba4cc06363469.png