洛谷1056列シート解題報告

3697 ワード

洛谷1056列シート
本題の住所: http://www.luogu.org/problem/show?pid=1056
タイトルの説明
授业の时にいつもいくつかの学友と前后の左右の人が耳を傾けて、これは小学校の担任を非常に悩ませる1件の事です.しかし、担任の小雪はいくつかの面白い现象を発见して、学友达の席次が确定した后に、限られたDだけが学友の授业の时に耳を傾けます.学生たちは教室の中でM行N列に座り、i行j列に座っている学生の位置は(i,j)で、学生たちの出入りを便利にするために、教室の中にK本の横方向の通路、L本の縦方向の通路を設置した.そこで、聡明な小雪は、授業中に学生が耳を傾ける問題を減らすことができるかもしれないと考えた.彼女はテーブルと椅子を並べ直して、学生たちのテーブルと椅子の間の通路の位置を変えるつもりだ.もし1つの通路が2人の耳をつなぐ学生を隔てていたら、彼らは耳を貸さないからだ.小雪にプログラムを作ってもらい、最高の通路区分案を出してください.この案では、授業中に耳を傾けた学生の対数が最も少ない.
にゅうしゅつりょくけいしき
入力形式:
入力ファイルseat.inの最初の行には、5つのスペースで区切られた整数があり、それぞれM,N,K,L,D(2<=N,M<=1000,0<=Kの次のD行であり、行ごとに4つのスペースで区切られた整数がある.i行目の4つの整数Xi,Yi,Pi,Qiは、位置(Xi,Yi)と(Pi,Qi)に座っている2人の同級生会が頭を合わせていることを示す(入力は、彼らが前後に隣接しているか、左右に隣接していることを保証する)..入力データは、最適なシナリオの一意性を保証します.
出力フォーマット:
出力ファイルseat.outは2行です.1行目はK個の整数、a 1,a 2......aKで、a 1行目とa 1+1行目の間、a 2行目とa 2+1行目の間、...、aK行目とaK+1行目の間にチャネルを開くことを示します.ai入出力サンプル
サンプル#1を入力:
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

出力サンプル#1:
2
2 4

説明
上の図では、3組の生徒の位置を記号*、※、+で示し、図中の3本の太い線の位置が通路を示し、図示した通路区分案が唯一の最良案である.2008年普及グループ第2題
問題解
シミュレーション
この問題の方法は比較的巧みで、学生のペアを読むときに、彼らの間に通路を追加する必要があるかもしれません.
チャネルは、(4,2)(4,3)チャネルが縦2であるなど、2人の学生の異なる座標値のうちの小さいものである.
まずそれを記録し,チャネルの使用回数に従って降順に出力し,出力が最適解であることを保証する.
コードを添付します.
コード#コード#
program seat;  
  • var  

  •   m,n,k,l,d,max,maxx,i,j:longint;  
  •   x,y,p,q:array[1..2000] of longint;  

  •   a,b,f,g:array[1..1000] of longint;  
  • function min(i,j:longint):longint;  

  •   begin  
  •     if i>j then min:=j  

  •     else min:=i;  
  •   end;  

  • begin  
  •   readln(m,n,k,l,d);  

  •   max:=0;  
  •   maxx:=0;  

  •   fillchar(f,sizeof(f),0);  
  •   fillchar(g,sizeof(g),0);  

  •   for i:=1 to d do  
  •     begin  

  •       readln(x[i],y[i],p[i],q[i]);  
  •       if y[i]=q[i] then inc(a[min(x[i],p[i])]);  

  •       if x[i]=p[i] then inc(b[min(y[i],q[i])]);  
  •     end;  

  •   for i:=1 to k do  
  •     begin  

  •       for j:=1 to m do  
  •         if a[j]>max then begin max:=a[j]; maxx:=j; end;  

  •       f[maxx]:=maxx;  
  •       for j:=1 to m do  

  •         if a[j]=max then begin a[j]:=0; break; end;  
  •       max:=0;  

  •     end;  
  •   for i:=1 to l do  

  •     begin  
  •       for j:=1 to n do  

  •         if b[j]>max then begin max:=b[j]; maxx:=j; end;  
  •       g[maxx]:=maxx;  

  •       for j:=1 to n do  
  •         if b[j]=max then begin b[j]:=0; break; end;  

  •       max:=0;  
  •     end;  

  •   for i:=1 to m-1 do  
  •     begin  

  •       if k=0 then break;  
  •       if f[i]<>0 then  

  •         begin  
  •           write(f[i],' ');  

  •           dec(k);  
  •         end;  

  •     end;  
  •   writeln;  

  •   for i:=1 to n-1 do  
  •     begin  

  •       if l=0 then break;  
  •       if g[i]<>0 then  

  •         begin  
  •           write(g[i],' ');  

  •           dec(l);  
  •         end;  

  •     end;  
  •   writeln;  

  • end.  
    (本文は筆者オリジナルで、許可なく転載してはならない)
    転載先:https://www.cnblogs.com/yzm10/p/4747522.html