逐价位建立关于补贴额 t 的一次不等式，取上下界交集后在可行区间中选绝对值最小的整数。
OJ: roj
题目 ID: 3499
难度:普及
标签:数学python
创建: 2026-10-02 03:29
更新: 2026-10-06 12:12
题目描述
已知商品成本 NO SOLUTION。
思路
每个可售价位
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 04:25
# update_at: 2026-10-02 04:25
import sys
from bisect import bisect_right
INF = 10**18 # 还没产生某一侧约束时的区间哨兵
PRICE_CAP = 300000 # 销量归零前的价位枚举上限（题面所有数字 < 100000）
def sales(xs: list[int], ss: list[int], drop: int, price: int) -> tuple[int, int]:
"""价位 price 的销量，返回 (分子, 分母)：已知价位间线性插值，超过最高价位后每涨 1 元减 drop。"""
i = bisect_right(xs, price) - 1 # price 落在 xs[i] ~ xs[i+1] 的插值段内
if i + 1 < len(xs):
p0, p1 = xs[i], xs[i + 1]
# 段内销量 = ss[i] + (ss[i+1]-ss[i])/(p1-p0) * (price-p0)，先不约分
return ss[i] * (p1 - p0) + (ss[i + 1] - ss[i]) * (price - p0), p1 - p0
return ss[i] - drop * (price - xs[i]), 1 # 超出最高价位：按固定数值递减
def ceil_div(a: int, b: int) -> int:
"""向上取整的整数除法，要求 b > 0。"""
return -((-a) // b)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
target = next(data) # 政府预期价
cost, low_sales = next(data), next(data) # 成本价、成本价位上的销量
known: dict[int, int] = {cost: low_sales} # 已知价位 → 销量，按价位去重
while True:
price, count = next(data), next(data)
if price == -1 and count == -1:
break
known[price] = count
drop = next(data) # 超出最高价位后每涨 1 元减少的销量
xs = sorted(known) # 升序价位表，供二分定位插值段
ss = [known[p] for p in xs]
if target < cost: # 预期价低于成本，产品不会在该价位销售
print("NO SOLUTION")
return
target_num, target_den = sales(xs, ss, drop, target)
if target_num <= 0: # 预期价位上没有销量，谈不上最大总利润
print("NO SOLUTION")
return
base = target - cost # 预期价位的不含税单位利润
lo, hi = -INF, INF # 补贴额 t 最终落在区间 [lo, hi]
for price in range(cost, PRICE_CAP + 1):
num, den = sales(xs, ss, drop, price)
if num <= 0: # 销量随价位单调不增，后面价位都没有销量
break
gain = price - cost # 该价位的不含税单位利润
# 要求 (base+t)·target_num/target_den ⩾ (gain+t)·num/den，
# 两边乘正数 target_den·den 后是关于 t 的一次不等式：
target_coef = target_num * den # 左边 t 的系数
price_coef = num * target_den # 右边 t 的系数
if target_coef == price_coef:
# 销量相同：不含税单位利润必须不低，否则任何 t 都救不回来
if gain > base:
print("NO SOLUTION")
return
elif target_coef > price_coef: # t 有下界
lo = max(lo, ceil_div(price_coef * gain - target_coef * base,
target_coef - price_coef))
else: # t 有上界
hi = min(hi, (price_coef * gain - target_coef * base)
// (target_coef - price_coef))
if lo > hi:
print("NO SOLUTION")
else:
# 区间内取绝对值最小：跨 0 取 0，否则取离 0 最近的端点
print(0 if lo <= 0 <= hi else min((lo, hi), key=abs))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 12:10
* update_at: 2026-10-06 12:10
*/
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int MAXP = 300000; // 价位扫描上限，防止销量永不归零时死循环
ll P; // 政府预期价
ll cost; // 商品成本
vector<ll> xs; // 升序已知价位表
vector<ll> ss; // 对应销量
ll drop; // 超过最高已知价位后每涨 1 元减少的销量
// 计算 a/b 的上取整，b != 0
ll ceil_div(i128 a, i128 b) {
i128 q = a / b;
i128 r = a % b;
if (r != 0 && ((r > 0) == (b > 0))) ++q;
return (ll)q;
}
// 计算 a/b 的下取整，b != 0
ll floor_div(i128 a, i128 b) {
i128 q = a / b;
i128 r = a % b;
if (r != 0 && ((r > 0) != (b > 0))) --q;
return (ll)q;
}
// 返回价位 p 的销量，以分数 num/den 表示（den > 0）
void get_sales(ll p, ll &num, ll &den) {
int i = upper_bound(xs.begin(), xs.end(), p) - xs.begin() - 1;
if (i + 1 < (int)xs.size()) {
ll p0 = xs[i], p1 = xs[i + 1];
den = p1 - p0;
num = ss[i] * den + (ss[i + 1] - ss[i]) * (p - p0);
} else {
den = 1;
num = ss[i] - drop * (p - xs[i]);
}
}
// 输出 __int128 整数
void print_i128(i128 x) {
if (x == 0) {
putchar('0');
return;
}
if (x < 0) {
putchar('-');
x = -x;
}
char buf[50];
int len = 0;
while (x > 0) {
buf[len++] = '0' + (int)(x % 10);
x /= 10;
}
while (len--) putchar(buf[len]);
}
int main() {
scanf("%lld", &P);
ll s0;
scanf("%lld%lld", &cost, &s0);
map<ll, ll> known;
known[cost] = s0;
while (true) {
ll p, s;
scanf("%lld%lld", &p, &s);
if (p == -1 && s == -1) break;
known[p] = s;
}
scanf("%lld", &drop);
for (auto &kv : known) {
xs.push_back(kv.first);
ss.push_back(kv.second);
}
// 预期价不能低于成本，否则产品不会在该价位销售
if (P < cost) {
printf("NO SOLUTION\n");
return 0;
}
ll t_num, t_den;
get_sales(P, t_num, t_den);
// 预期价位上没有销量，谈不上最大总利润
if (t_num <= 0) {
printf("NO SOLUTION\n");
return 0;
}
ll base = P - cost; // 预期价位的不含税单位利润
i128 lo = 0, hi = 0;
bool has_lo = false, has_hi = false;
// 从成本价开始逐价位扫描，销量非正即停止
for (ll p = cost; p <= MAXP; ++p) {
ll num, den;
get_sales(p, num, den);
if (num <= 0) break;
ll gain = p - cost;
// 要求 (base+t) * t_num/t_den >= (gain+t) * num/den
i128 target_coef = (i128)t_num * den; // 左边 t 的系数
i128 price_coef = (i128)num * t_den; // 右边 t 的系数
if (target_coef == price_coef) {
// 销量相同：该价位不含税单位利润不能更高，否则任何 t 都无法使 P 最大
if (gain > base) {
printf("NO SOLUTION\n");
return 0;
}
} else if (target_coef > price_coef) {
// t 有下界
i128 rhs = (i128)price_coef * gain - (i128)target_coef * base;
i128 dif = target_coef - price_coef; // > 0
i128 bound = ceil_div(rhs, dif);
if (!has_lo || bound > lo) {
lo = bound;
has_lo = true;
}
} else {
// t 有上界
i128 rhs = (i128)price_coef * gain - (i128)target_coef * base;
i128 dif = target_coef - price_coef; // < 0
i128 bound = floor_div(rhs, dif);
if (!has_hi || bound < hi) {
hi = bound;
has_hi = true;
}
}
}
// 无可行补贴额
if (has_lo && has_hi && lo > hi) {
printf("NO SOLUTION\n");
return 0;
}
i128 ans;
if ((!has_lo || lo <= 0) && (!has_hi || hi >= 0)) {
ans = 0; // 可行区间包含 0，取绝对值最小
} else if (has_hi && hi < 0) {
ans = hi; // 全负，取右端点
} else {
ans = lo; // 全正，取左端点
}
print_i128(ans);
putchar('\n');
return 0;
}