POJ 2549 : Sumsets
問題
要素数N()の数列が与えられる。この中でa+b+c=dを満たす最大のdを求めよ。
解法
a+bを全列挙し、d-cを二分探索する。a+bで選んだ要素とd-cで選んだ要素は互いに違わなければならない。値と共に、インデックスを持たせることで同じ要素を使ってる場合を除外する。
計算量
N : 要素数
要素数N()の数列が与えられる。この中でa+b+c=dを満たす最大のdを求めよ。
a+bを全列挙し、d-cを二分探索する。a+bで選んだ要素とd-cで選んだ要素は互いに違わなければならない。値と共に、インデックスを持たせることで同じ要素を使ってる場合を除外する。
N : 要素数