Codeforces Round #352 (Div. 2) D. Robin Hood

問題

Problem - D - Codeforces
長さNの数列がある。
数列の最大の要素から1引き、最小の要素に1足すのをK回繰り返す。
(候補が複数ある場合はランダムに選ばれるが、問題文にもある通り答えには影響しない)
最終的な数列の(最大値)-(最小値)を求めよ。

解法

追記 二分探索しましょう

簡単にするためにとりあえず数列をソートする。
最小値と最大値の差が1以下になる((3,3,3,2,2)みたいな状態になる)までの最小の操作回数を求め、Kがそれ以上の場合は(3,3,3,2,2)みたいなのをそのまま答えにする。
そうでない場合、シミュレートを頑張る。
K回を超えないまでは、最大値/最小値を揃えていく感じでまとめてシミュレートできる。
するとになる。

実装

最初に場合分けをしたから、シミュレートが行き過ぎない(差が1以下になるまでは操作しない)ことが分かっているので、最大値側からと最小値側からで2回シミュレートすると楽かも。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_N = 30;

int N, D;

struct Treasure
{
	int x, y;
	Treasure() { x = y = 0; }
	Treasure(int _x, int _y) { x = _x; y = _y; }
	Treasure operator + (const Treasure &t) const
	{
		return Treasure(x + t.x, y + t.y);
	}
	Treasure operator - (const Treasure &t) const
	{
		return Treasure(x - t.x, y - t.y);
	}
	bool operator < (const Treasure &d) const
	{
		return x < d.x;
	}
};

Treasure treasure[MAX_N];

void DFS(int l, int r, Treasure sum, vector<Treasure> &res)
{
	if (l == r)
	{
		res.push_back(sum);
		return;
	}
	DFS(l + 1, r, sum, res);
	DFS(l + 1, r, sum + treasure[l], res);
	DFS(l + 1, r, sum - treasure[l], res);
}

int sum[20000000];

signed main()
{
	cin >> N >> D;
	for (int i = 0; i < N; i++)
	{
		cin >> treasure[i].x >> treasure[i].y;
	}
	vector<Treasure> s, t;
	s.reserve(20000000); t.reserve(20000000);
	DFS(0, N / 2, Treasure(), s);
	DFS(N / 2, N, Treasure(), t);
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	int ans = -LLONG_MAX;
	{
		int l = 0, r = 0;
		deque<int> dq;
		for (int i = t.size() - 1; i >= 0; i--)
		{
			while (r < s.size() && s[r].x + t[i].x <= D)
			{
				while (!dq.empty() && s[dq.back()].y <= s[r].y) dq.pop_back();
				dq.push_back(r);
				r++;
			}
			while (l < s.size() && s[l].x + t[i].x < -D)
			{
				if (!dq.empty() && dq.front() == l) dq.pop_front();
				l++;
			}
			if (!dq.empty()) ans = max(ans, t[i].y + s[dq.front()].y);
		}
	}
	printf("%lld\n", ans);
	return 0;
}