专栏文章

题解：P10730 [NOISG 2023 Qualification] Burgers

EError_Eric
P10730题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miq836r7
此快照首次捕获于
2025/12/04 00:29
3 个月前
此快照最后确认于
2025/12/04 00:29
3 个月前
查看原文

Statement

为了避免歧义，这里用 x,yx, y 分别指代两种糖数量，用 cic_i 表示原文 xix_i。
可以认为是 ∀i,aix+biy≤ci\forall i, a_i x + b_i y \le c_i， 求最大的 x+yx + y。

Sol

几何意义上这是求一个（二维）凸包内 x+yx+y 最大的点，可以用一些很 fancy 的算法解决，但是都很难。考虑转化一下。
二分答案，假设 x+y=dx + y = d。思考下怎么验证。
可以通过消掉 yy 的方式求出 xx 的范围。
&a_ix + b_i y \le c_i \\ \Rightarrow & (a_i - b_i) x + b_i(x+y) \le c \\ \Rightarrow & (a_i - b_i) x \le c - b_i d \\ \end{aligned}
分类讨论 ai−bia_i - b_i。不难得到
{x≤c−bidai−bi    ai>bi0≤c−bid    ai=bix≥c−bidai−bi    ai<bi\begin{cases} x &\le \dfrac{c-b_id}{a_i - b_i} & \ \ \ \ a_i > b_i\\ 0 &\le c - b_id & \ \ \ \ a_i = b_i \\ x &\ge \dfrac{c-b_id}{a_i - b_i} & \ \ \ \ a_i < b_i\\ \end{cases}
check 的时候只需要保证第二种情况得到满足，第一、三种解出来不是空集就可以。当然注意 xx 是整数，第一种情况下商直接下取整，第二种上取整即可。

Code

CPP
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
using namespace std;
int n, ans = 0;
vector<long long> a, b, c;
bool check(int d){ // if x + y = d has solution
	long long maxx = d, minx = 0;
	for(int i = 0; i < n && minx <= maxx; i++){
		if(a[i] > b[i]) 
			maxx = min(maxx, (c[i] - b[i] * d) / (a[i] - b[i]));
		else if (a[i] < b[i])
			minx = max(minx, (c[i] - b[i] * d -1) / (a[i] - b[i]) + 1);
		else if (a[i] * d > c[i]) return false;
	}
	return minx <= maxx;
}
int main(){
	ios::sync_with_stdio(0),
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(auto vec:{&c, &a, &b}){
		vec->resize(n);
		for(long long&vx:(*vec))
			cin >> vx;
	}
	for(int k = (1<< 30); k; k>>=1){
		if(ans + k < 1e9 && check(ans+k))
			ans += k;
	}
	cout << ans << endl;
}

评论

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

正在加载评论...