饥饿的WZK

发布于 2019-04-05  984 次阅读


题目描述

【题目背景】
一中食堂的格局,同别处不大一样,都是当门一个曲形的大窗口,里面是各式各样的饭菜。平时吃饭总是叫人活泼不得,只有WZK来的时候才能偶尔欢快一下。
【问题描述】
同学们在食堂窗口前排好了队。食堂窗口依次用1到N编号。每天晚上,一个幸运的同学根据WZK的规则,买其中一些窗口里的饭菜。
WZK提供B个区间的清单。一个区间是一对整数start-end,1<=start<=end<=N,表示一些连续的食堂窗口,比如1-3,7-8,3-4等等。同学们可以任意选择区间,但是同学们选择的区间不能有重叠。
当然,同学们希望自己能够吃得越多越好。现在给出一些区间,请你编程帮助这位同学找一些区间,使他能吃到最多的东西。
在上面的例子中,1-3和3-4是重叠的。聪明的你应该选择{1-3,7-8},这样可以吃到5个窗口里的东西。

输入

第一行,整数B。
第2到B+1行,每行两个整数,表示一个区间,较小的端点在前面。

输出

一行一个整数,表示他最多能吃到多少个窗口里的食物。

思路

就是一个贪心的做法。。。

const
  maxn=5000;
var
  b,e,f:array[1..maxn] of longint;
  i,n,t,j,m:longint;
  ans:int64;

procedure qsort(l,r:longint);
  var
    i,j,key,temp,mid:longint;
  begin
    if l>=r then exit;
    i:=l;j:=r;
    key:=b[(l+r) div 2];
    mid:=e[(l+r) div 2];
    repeat
      while  (b[i]e[i])) do inc(i);
      while  (b[j]>key) or ((b[j]=key)and(midj;
   if j>l then qsort(l,j);
   if ie[j])
        then f[i]:=f[j]+e[i]-b[i]+1;
    end;
    end;
  for i:=1 to n do
    if m
]]>