最大访问量pascal

来源：百度知道 编辑：UC知道 时间：2024/05/31 15:42:32
愚人节宴会中一共有 n 位来宾，小田田依照来宾的到达与离去的登记时间，第 i 位来宾在 Xi 时到达，在 Yi 时离开，因此第 i 位来宾在宴会场中的时间是 [ xi , Yi) ，亦即 xi <= t < Yi 中所有可能的 t ，请写一个程序，读入xi 与Yi , 1 <= i <= n ，帮助小田田找出同一时刻最多会有多少人同时在宴会场中。
第一行是来宾数 n ( n <=1000）剩余各行分别是 n 位来宾的到达和离去时间 xi 、yi <50000同一时刻访问该宴会的来宾最大值
输入
3
1 4
2 3
1 5
输出
3

这个叫贪心? 大致是这样:先把所有N*2个时间点排序,然后按顺序从左到右,碰到一个来的人就把当前人数+1,碰到一个走的人就把当前人数-1(注意处理相同的时间点),每修改一次就更新一下答案.
不知道能不能理解:-)

再说下 穷举也许能过 但这题的做法就是上面这样讲的
穷举是O(nT)的
排序是O(nlogn)的 把n和T改成一百万都可以

没时间写，就写个伪代码给你，你能看懂吧
//穷举,直接找出最大的循环量t1(最迟走的宾客走的时间),
begin
for i:=1 to t1 do
for j:=1 to n do
begin
看看有多少宾客在这个时间访问在宴会现场；
if 访问量>max then max:=访问量；
end;
输出max;
end.

这个程序可以在1秒钟内运行完。

第二次回答！

===================================
var
a:array[1..1001,1..2]of integer//a[x,1]是来的时间,a[x,2]是走的时间
i,j:integer;
max:integer;
begin
readln(n);
for i:=1 to n do
readln(a[i,1],a[i,2]);
for i:=1 to n do
if a[i,2]>max then a[i,2]:=max;
for i:=1 to t1 do
begin
for j:=1 to n do
begin
if a[i,1]<j and a[i,2]>j then sum:=sum+1；//sum就是访问量
end;
if sum>max then max:=sum；
end;
writeln(max);
e