专栏文章

题解：P8244 [COCI 2013/2014 #3] KOLINJE

CCaYi
P8244题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miobuk2q
此快照首次捕获于
2025/12/02 16:39
3 个月前
此快照最后确认于
2025/12/02 16:39
3 个月前
查看原文

题目

p8244

解析

根据题意定义 s=∑i=1nbis=\sum\limits_{i=1}^nb_i。

我们先考虑对于任意两个人的情况。

对于第 ii 个人和第 jj 个人（i<ji < j），要做到排名中 ii 在 jj 前面。
如果 ai<aja_i < a_j，那么若 bi≤bjb_i ≤ b_j，必然无解，因为一个人之前吃的就比你多，后面分到的还大于等于你被分到的，你是必不可能排在他前面的。
接下来考虑有解的情况，如果 ai<aja_i < a_j，bi>bjb_i > b_j，那么答案的下界就是方程 ai+x×bis=aj+x×bjsa_i + x \times\dfrac{b_i}s = a_j + x \times\dfrac{b_j}s 的解，当最终拿去分的火腿总量大于等于这个临界状态时，这两个人的排名顺序是对的，即 ii 排在 jj 前面。
同理，如果 ai>aja_i > a_j，bi<bjb_i < b_j，那么答案的上界依旧是方程 ai+x×bis=aj+x×bjsa_i + x \times\dfrac{b_i}s = a_j + x \times\dfrac{b_j}s 的解，当最终拿去分的火腿总量小于等于这个临界状态时，这两个人的排名顺序是对的，即 ii 排在 jj 前面。

考虑全局

比较显然的思想，使用两个变量 lowlow 和 upup 存储全局答案的下界和上界。我们枚举每一个人与编号在他后面的人，依照考虑两个人的情况的方法，判断有无解，以及计算上下界，lowlow 取 max⁡\max，upup 取 min⁡\min，可以做到确定全局满足要求的上下界范围。最后判断 low≤uplow ≤ up，否则无解。输出 low+up2\dfrac{low + up}2 即可。
复杂度 O⁡(n2)\operatorname{O}(n ^ 2)，可以通过。
注意精度问题，多输出几位小数。

Code time

CPP
/*
code by : CaYi
*/
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
//using i128 = __int128;

const int N = 1e3 + 6;

int n;
double a[N], b[N], s;
double low = 0, up = 1e7;

int main() {
	std::cin.tie(nullptr) -> sync_with_stdio(false);
	
	std::cin >> n;
	
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i] >> b[i];
		s += b[i];
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (a[i] < a[j] && b[i] <= b[j]) {
				std::cout << -1 << '\n';
				return 0;
			} else if (a[i] < a[j] && b[i] > b[j]) {
				low = std::max(low, (a[j] - a[i]) / (b[i] - b[j]) * s);
			} else if (a[i] > a[j] && b[i] < b[j]) {
				up = std::min(up, (a[i] - a[j]) / (b[j] - b[i]) * s);
			}
		}
	}
	
	if (low > up) {
		std::cout << -1 << '\n';
		return 0;
	} else {
		std::cout << std::fixed << std::setprecision(11) << (low + up) / 2 << '\n';
	}
	
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...