値でソートしたのを a[0]..a[n-1] とします.
差が d 以下で作れるペアの最大数を求めたいです.
これがわかると, d で二分探索し, 作れるペアが P 以上な最小の d を求めればよいです.
 
a[1] - a[0] が d 以下なら, これをペアにしてよいです, なぜなら:
  1 < i < j な i, j を持ってきて a[0] と a[i], a[1] と a[j] をペアにするなら,
  a[0] と a[1], a[i] と a[j] もペアに出来て, これでもペアの個数は変わらない.
 
  1 < i な i を持ってきて, a[0] と a[i] をペアにしたり, a[1] と a[i] をペアにするなら,
  a[0] と a[1] をペアにしてもペアの個数が変わらない.
 
なので, a[1] - a[0] <= d なら, 1 + (a[2] 以降の解) が求める最大数です.
 
一方, a[1] - a[0] > d なら, a[0] は誰ともペアになれないので, (a[1] 以降の解) が求める最大数です.
 
 

5YCk44Gn44K944O844OI44GX44Gf44Gu44KSIGFbMF0uLmFbbi0xXSDjgajjgZfjgb7jgZkuCuW3ruOBjCBkIOS7peS4i+OBp+S9nOOCjOOCi+ODmuOCouOBruacgOWkp+aVsOOCkuaxguOCgeOBn+OBhOOBp+OBmS4K44GT44KM44GM44KP44GL44KL44GoLCBkIOOBp+S6jOWIhuaOoue0ouOBlywg5L2c44KM44KL44Oa44Ki44GMIFAg5Lul5LiK44Gq5pyA5bCP44GuIGQg44KS5rGC44KB44KM44Gw44KI44GE44Gn44GZLgoKYVsxXSAtIGFbMF0g44GMIGQg5Lul5LiL44Gq44KJLCDjgZPjgozjgpLjg5rjgqLjgavjgZfjgabjgojjgYTjgafjgZksIOOBquOBnOOBquOCiToKICAxIDwgaSA8IGog44GqIGksIGog44KS5oyB44Gj44Gm44GN44GmIGFbMF0g44GoIGFbaV0sIGFbMV0g44GoIGFbal0g44KS44Oa44Ki44Gr44GZ44KL44Gq44KJLAogIGFbMF0g44GoIGFbMV0sIGFbaV0g44GoIGFbal0g44KC44Oa44Ki44Gr5Ye65p2l44GmLCDjgZPjgozjgafjgoLjg5rjgqLjga7lgIvmlbDjga/lpInjgo/jgonjgarjgYQuCiAgCiAgMSA8IGkg44GqIGkg44KS5oyB44Gj44Gm44GN44GmLCBhWzBdIOOBqCBhW2ldIOOCkuODmuOCouOBq+OBl+OBn+OCiiwgYVsxXSDjgaggYVtpXSDjgpLjg5rjgqLjgavjgZnjgovjgarjgoksCiAgYVswXSDjgaggYVsxXSDjgpLjg5rjgqLjgavjgZfjgabjgoLjg5rjgqLjga7lgIvmlbDjgYzlpInjgo/jgonjgarjgYQuCgrjgarjga7jgacsIGFbMV0gLSBhWzBdIDw9IGQg44Gq44KJLCAxICsgKGFbMl0g5Lul6ZmN44Gu6KejKSDjgYzmsYLjgoHjgovmnIDlpKfmlbDjgafjgZkuCgrkuIDmlrksIGFbMV0gLSBhWzBdID4gZCDjgarjgoksIGFbMF0g44Gv6Kqw44Go44KC44Oa44Ki44Gr44Gq44KM44Gq44GE44Gu44GnLCAoYVsxXSDku6XpmY3jga7op6MpIOOBjOaxguOCgeOCi+acgOWkp+aVsOOBp+OBmS4KCg==