ABC432C 分糖果2
大约 4 分钟数学
ABC432C 分糖果2
【算法标签】 数学推导/数论
【语法标签】 :数组、for循环
- 小糖果重 X 克,大糖果重 Y 克(),数量无限
- 有 N 个孩子,第 i 个孩子必须得到 颗糖果(总数)
- 每个孩子的糖果总重量必须相等
- 问:是否存在这样的分发方式?如果存在,求大糖果总数的最大值;否则输出
-1
二、核心思路:最大化总重量 W
2.1 建立方程
设每个孩子的总重量为 W,第 i 个孩子拿到 颗大糖果、 颗小糖果:
消去 得:
2.2 要最大化大糖果数,就要最大化 W
因为 ,、、 都是常数,所以 W 越大,大糖果总数越多。
2.3 W 的上界
由 可得:
对所有 i 同时成立,所以:
结论:令 ,则最优 (让糖果数最少的孩子拿满大糖果)。
三、逐块解析代码
#include<bits/stdc++.h>
using namespace std;
long long n,x,y,ans,sum;
long long a[200005];
int main(){
cin >> n >> x >> y;
ans = INT_MAX;
for (int i = 1;i <= n; i++){
cin >> a[i];
sum += a[i];
ans = min(ans,a[i]);
}
long long l = y - x;
for (int i = 1;i <= n; i++){
long long k = (a[i] - ans) * y;
if(a[i]*x > ans*y){
cout << "-1";
return 0;
}
if(k%l == 0){
sum = sum - (k/l);
}else{
cout << "-1";
return 0;
}
}
cout << sum;
return 0;
}3.1 读入与初始化
long long n, x, y, ans, sum;
long long a[200005];
cin >> n >> x >> y;
ans = INT_MAX;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum += a[i]; // 累加数组总和 ΣA_i
ans = min(ans, a[i]); // 找出最小值 min(A_i)
}ans:数组最小值,即sum:数组总和,即
3.2 计算差值
long long l = y - x; // D = Y - X3.3 逐个校验并累减
for (int i = 1; i <= n; i++){
long long k = (a[i] - ans) * y;
// 检查 ①:A_i * X > ans * Y 则无解
if (a[i] * x > ans * y){
cout << "-1";
return 0;
}
// 检查 ②:(A_i - ans) * Y 必须能被 (Y - X) 整除
if (k % l == 0){
sum = sum - (k / l); // 累减
}
else{
cout << "-1";
return 0;
}
}
cout << sum;两个校验条件的含义:
| 条件 | 数学含义 | 直觉理解 |
|---|---|---|
a[i] * x > ans * y | i 号孩子全拿小糖果的重量 > 最小孩子全拿大糖果的重量,无法平衡 | |
k % l != 0 | 不能被 整除 | 小糖果数不是整数,无法分配 |
3.4 就是小糖果数
已知 ,,则小糖果数:
所以代码的逻辑是:
sum = ΣA_i // 总糖果数
对于每个孩子 i:
sum -= a_i // 减去小糖果数
最终 sum = ΣA_i - Σa_i = Σb_i // 剩下的就是大糖果总数代码用累减法,本质上是"总糖果数 - 小糖果总数 = 大糖果总数"。
四、整除等价性说明
代码检查的是 ,而非 。两者等价吗?
是的,因为:
两者之差为:
模 下,可以验证两者同余:
和 互为相反数,模 下同余于 0 的条件完全相同。
五、时间复杂度
- 时间:,单次遍历完成所有计算
- 空间:,存储输入数组
六、关键洞察总结
- 最大化 W = 最小值 × Y:让糖果数最少的孩子拿满大糖果,此时总重量最大
- 累减法:初始 sum 为总糖果数,逐个减去调整量,最终 sum 恰好等于大糖果总数
- 两个必要条件:重量上限约束 + 整除约束,缺一不可
