091119的第四题【欧阳建昭吧】

欧阳建昭吧关注：8贴子：81

3回复贴，共1页

091119的第四题

彩色(color)
[题目描述]
  在直角坐标系上，有N个边平行于坐标轴的矩形。你的任务是把其中的K个矩形染色，使按次序放下后，可以看见的有色面积最大。可看见的意思就是这一部分没有被后面的矩形覆盖。
  你的答案是返回K个整数，表示你染色的是哪K个矩形。如果有多种答案，输出字典序最小的。
[数据范围]
  1<=N<=50； 1<=K<=N。
  每个坐标值为[-10000,10000]之间的整数。
[输入文件 color.in]
  第一行两个整数：N K
  后面有N行，每行4个整数: x1 y1 x2 y2, 分别表示先后各个矩形的左下角坐标和右上角坐标。

[输出文件 color.out]
  一行，K个整数：你的方案。
样例
输入 3  2
1 1 5 3
3 2 7 4
2 5 9 7 7  4
1 1 5 4
2 2 4 3
4 0 6 2
7 1 9 4
1 5 4 7
6 5 9 7
2 5 8 6
输出 1 2 0 2 3 6

送TA礼物

IP属地:四川

1楼2009-11-19 15:15回复

标程
type
   aa  = array[0..110] of longint;
var
  N, K :longint;
  map :array[0..110, 0..110] of boolean;     //  离散化后的方格，有没有被覆盖

  x1, x2,y1,y2,                                             //坐标，离散化后则为序号（第几大）
  xx, yy      : aa;                                           //排序、离散化用，记录
  s  : array[0..51] of longint;                       //记录每张纸可视的面积
procedure sort(var xx, x1,x2: aa) ;           //把x1,x2中的坐标离散化
var  i,j,tmp :longint;
begin
   xx:=x1;   for i:=1 to N do xx[N+i]:=x2[i];   //把x1和x2中的数复制到xx中
   for i:=1 to 2*N do                                     //对xx排序，N大时要快排
     for j:=i+1 to 2*N do
        if xx[i] > xx[j] then
begin
           tmp:=xx[i]; xx[i]:=xx[j]; xx[j]:=tmp;
end;
    for i:=1 to N do                         //对x1换成序号。N大时如何？
       for j:=1 to 2*N do                  //N大时，xx中记录原位置或二分查找
         if x1[i]=xx[j] then
begin
              x1[i] := j ; break;
end;
    for i:=1 to N do
       for j:=1 to 2*N do               //对x2换成序号

IP属地:四川

2楼2009-11-19 15:17

         if x2[i]=xx[j] then
begin
              x2[i] := j ; break;
end;
end;
procedure readin;
var i:longint;
begin
   readln(N, K);
   for i:=1 to N do
    readln(x1[i], y1[i], x2[i], y2[i] );
   sort(xx,x1,x2);       //对x轴离散化
   sort(yy,y1,y2);       //对Y轴离散化
end;
procedure work;
var p, sum,i,j,tmp :longint;
begin
  for p:=N downto 1 do  //从最上面到最下面处理
  begin
    sum :=0;                     //求当面纸被看见的面积
    for i:=x1[p]+1 to x2[p] do
      for j:= y1[p]+1 to y2[p] do
        if map[i,j]=false then
begin
   map[i,j]:=true;     //把这个“方格”盖住
   sum := sum +(xx[i] - xx[i-1])*(yy[j] - yy[j-1]);
end;
      s[p]:=sum;
    end;
end;
procedure print;
var
  i,j,tmp,maxi:longint;
  ans:array[1..51] of longint;
begin
   for i:=1 to k do   //找最大可视面积的K张纸
   begin
      maxi:=1;
      for j:=1 to N do
        if s[maxi] <s[j] then maxi:=j;
      ans[i]:=maxi-1;
      s[maxi]:=-1;
   end;
   for i:=1 to  K do   //排序，字典序最小输出
     for j:=i+1 to K do
       if ans[i]> ans[j] then
         begin tmp:=ans[i]; ans[i]:=ans[j]; ans[j]:=tmp; end;
   for i:=1 to K-1 do  write(ans[i],' ');
   writeln(ans[k]);
end;
begin
   assign(input,'color.in'); reset(input);
   assign(output,'color.out'); rewrite(output);
   readin;
   work;
   print();
   close(output);
end.
顶欧阳，一等奖
二十一，虐仓惶

IP属地:四川

3楼2009-11-19 15:17