fork download
copy 
  1. 値でソートしたのを a[0]..a[n-1] とします.
  2. 差が d 以下で作れるペアの最大数を求めたいです.
  3. ペアの数が最大のもので, 各ペアがソート順で隣り合っているものがあることを示します.
  4.  
  5. 最適解を一つ持ってきます.
  6. この解で隣り合わないペア (a[i], a[j]) (i<j) のうち, i が最も小さいものを持ってきます.
  7.  
  8. a[i+1] が誰ともペアでないなら, このペアの代わりに (a[i], a[i+1]) をペアにすればよいです.
  9. x = i+1 とし, a[x] とペアなのを a[y] とします.
  10. すると, min{i, j, x, y} = i です. (x は x+1 とペアか, 隣り合わないものとペアで, (a[i], a[j]) は隣り合わない最初のペアだった.)
  11.  
  12. i < x < j < y か, i < x < y < j です.
  13. どちらの場合も, (a[i], a[x]) と (a[j], a[y]) をペアに出来ます:
  14.  
  15.     前者の場合, 下図のように,
  16.     a[x]-a[i] <= a[j]-a[i] かつ a[y]-a[j] <= a[y]-a[x]
  17.            |-----|            |--|
  18.         i  x  j  y  =>  i  x  j  y
  19.         |-----|         |--|
  20.  
  21.     後者の場合, 下図のように,
  22.     a[x]-a[i] <= a[j]-a[i] かつ a[y]-a[j] <= a[j]-a[i]
  23.  
  24.            |--|               |--|
  25.         i  x  y  j  =>  i  x  j  y
  26.         |--------|      |--|
  27.  
  28. なので, a[i] とのペアが隣り合うようにできました.
  29. これを繰り返せば, 全部隣り合うように出来ます.
  30.  
  31.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ailnv9
language:
Text (text 6.10)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!