自动搬运

查看原文

来自洛谷，原作者为

	BFSBFSBFSBFS **

搬运于2025-08-24 21:35:39，当前版本为作者最后更新于2017-12-28 08:45:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

贪心题.写证明.

题意.给出$n$个节目.每个节目有开始时间$a_i$与结束时间$b_i$.

$a_i > b_j$的2个节目不能放在1组.$(1 <= i,j <= n)$.

求2组.最大化节目数量..

贪心策略:

....按照结束时间排序.

....若节目可以放.则必定放.

....尽量放在结束时间长的1组.

证明:

....对于其中1组.设它结束时间为$p$.

....若有$p <= a_i$.则该节目可以放在这组上.

....我们希望结束时间越小越好.用来放置更多的节目.

....那么取$p = min(b_i), (p <= a_i, 1 <= i <= n)$.

....若有$b_j$同样满足$(p <= a_j, 1 <= j <= n)$.

....用$b_j$代替$b_i$.

....那么节目总个数不会变.

....因$b_i <= b_j$.$p$可能增大.并非最优.

....所以按结束时间排序的思想正确.

....从2组的角度来看.

....若要使节目数+1.

....$p_1$与$p_2$必然存在1个$p = min(b_i)$.

....所以若$p_1 < p_2$.且$p_2 <= a_i, (1 <= i <= n)$.

....放在$p_1$则留下$p_2, b_i$.

....放在$p_2$则留下$p_1, b_i$.

....因为$p_1 < p_2$.

....放在$p_2$更优.

完毕.

还是很假.

Diu代码.

program P2255;
 var
  a,b:array[0..151] of longint;
  i,j,n,t,t1,s:longint;
 begin
  readln(n);
  for i:=1 to n do
   readln(a[i],b[i]);       //开始与结束时间....
  for i:=1 to n-1 do        //按结束时间排序....
   for j:=i+1 to n do
    if (b[i]>b[j]) or (b[i]=b[j]) and (a[i]>a[j]) then
     begin
      t:=b[i];
      b[i]:=b[j];
      b[j]:=t;
      t:=a[i];
      a[i]:=a[j];
      a[j]:=t;
     end;
  t:=0;
  t1:=0;                    //2组分别的结束时间.
  s:=0;                     //具体节目数量..
  for i:=1 to n do
   if a[i]>=t then          //能放在第1组..
    begin
     inc(s);
     if (t1>=t) and (a[i]>=t1) then t1:=b[i] //第2组能放.且更优..
                               else t:=b[i];
    end
              else if a[i]>=t1 then          //能放在第2组..
    begin
     inc(s);
     t1:=b[i];
    end;
  writeln(s);
 end.

(ಡωಡ).