私はこの問題を解決しようとしています: http://acm.tju.edu.cn/toj/showp2886.html
いくつかの解決策を試しましたが、そのうちの 2 つについて説明します。両方とも、コスト (位置) が凸関数であると仮定していることに注意してください。つまり、中央に向かって減少し (実際には、中央値 (供給ポイント) に向かってどこか)、グラフは多かれ少なかれ U 字型のように見えます。
cost(position) <= M である供給ポイントの左端と右端の位置を見つけます。最小値と最大値を見つけた後、間隔を少し大きくできるかどうかを確認します (レストランは場所である必要はないため)。正確に供給ポイントに）。これは良い解決策ですが、最後のビットを計算するのに非常に時間がかかります。M が非常に大きく、最小コストの供給ポイントがほとんどないテストでは失敗します。複雑さ: O(NlogN) + O(M)。以下のこの解決策はそのままで時間制限を超えていますが、O(1) で両方向にどれだけ移動できるかを計算する別の解決策を試してみましたが、間違った答えが得られました。
この関数は凸関数であるため、三項検索を使用して最小値を見つけることができます。最小値が M 未満の場合、関数の下限と上限 (つまり M) をバイナリ検索します。複雑さ: O(NlogM) すべての O(logM) に対して、O(N) でコストを計算するためです。
これは私が試したものであり、まだ「間違った答え」が得られるので、これが私を狂わせているので、助けが必要です.
最初にそれを読んだとき、コストがすべての供給ポイントから計算されたのではなく、最も近いものから計算されたと思ったので、問題は仕様で実際には明確ではありません (少なくとも私はそう思います)。例はそれをクリアしました。また、コスト（位置）関数が凸であるという私の仮定が本当に正しいかどうかもわかりません。しかし、私は多くの例を試しましたが、そうです。
ありがとう。どんな助けでも大歓迎です。:D