SRM684 Div1 Easy "CliqueParty"
解法
配列を昇順にソートしておいて、サブセットに含める最小値a[L]と最大値a[R]の2つを決め打ちする。
すると、Dの最大値は「a[R] - a[L]」に固定される。Dの最小値も「Dの最大値 / k」に固定される。
あとはa[L + 1]からa[R - 1]まで順に走査し、最近使用した左のものとの差、およびa[R]との差がDの最小値以上のものを貪欲に選んでいけばよい。
ソースコード
class CliqueParty { public: int maxsize(vector<int> a, int k) { int n = a.size(); sort(a.begin(), a.end()); int ans = 2; for (int L = 0; L < n; L++) { for (int R = L + 1; R < n; R++) { // (i, j)の範囲内とする。 int ma = a[R] - a[L]; int mi = ma / k + (ma % k == 0 ? 0 : 1); // 貪欲に行こう int cnt = 0; int pre_val = a[L]; for (int i = L + 1; i < R; i++) { if (mi <= a[i] - pre_val && mi <= a[R] - a[i]) { cnt++; pre_val = a[i]; } } if (ans < 2 + cnt) { ans = 2 + cnt; } } } return ans; } };