题解：P12360 [eJOI 2024] 足球决斗 / CF Duels

显然得到的信息越多越容易确定胜利，因此答案具有单调性，考虑二分并检验得到信息的场馆数量

mid

。

因为我们可以在比赛开始后再安排双方球员的对阵关系，所以不确定性来源于一对对阵取得的收益来自哪个场馆不确定。然后就是经典的田忌赛马策略：将双方球员和场馆按权值升序排列，逐一考虑己方队员，考虑他能战胜的所有对手并分情况讨论。若选择的对手来自已知的场馆那么收益是确定的，这种情况容易处理。若选择的对手来自未知的场馆，则取其中的最小收益累加。考虑完所有球员后判断能否取得冠军。若最小收益足以战胜对手则说明能否获胜与对方的安排无关，可以必胜，因为我们考虑了对方采取最佳的安排将我方收益最小化时的情况。

用一个大根堆维护所有可能的对阵情况，每次取出堆顶对阵方案即可。

CPP

const ll N = 5e4 + 10;
ll n, sum, a[N], v[N];
pll sta[N], player[N];
pqueue(ll, less) pq;

#define jump1 for(;a[i]>player[p1].fi and p1<=n;p1++)
#define jump2 while(sta[p2].se<=k and p2<=n)p2++;

bool check(ll k) {
	myclear(pq);
	ll pts = 0, p1 = 1, p2 = 1;
	jump2;

	rep(i, 1, n) {
		jump1{
			if (player[p1].se <= k)
				pq.push(v[player[p1].se]);
			else {
				pq.push(sta[p2].fi);
				p2++;
				jump2;
			}
		}

		if (pq.size()) {
			pts += pq.top();
			pq.pop();
		}
	}

//	cout << "pts=" << pts << '\n';
//	pause;
	return pts > sum - pts;
}

int main() {
	cin >> n;

	rep(i, 1, n) {
		cin >> v[i];
		sta[i] = {v[i], i};
		sum += v[i];
	}

	sort(sta + 1, sta + n + 1);

	rep(i, 1, n) {
		cin >> player[i].fi;
		player[i].se = i;
	}

	sort(player + 1, player + n + 1);

	rep(i, 1, n) cin >> a[i];

	sort(a + 1, a + n + 1);

	ll l = 0, r = n, ans = -1;

	while (l <= r) {
		ll mid = (l + r) / 2;

		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else
			l = mid + 1;
	}

	cout << ans;
}

题解：P12360 [eJOI 2024] 足球决斗 / CF Duels

文章操作

相关推荐

评论

题解：P12360 [eJOI 2024] 足球决斗 / CF Duels