专栏文章
题解:P1023 [NOIP 2000 普及组] 税收与补贴问题
P1023题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miq8yksq
- 此快照首次捕获于
- 2025/12/04 00:54 3 个月前
- 此快照最后确认于
- 2025/12/04 00:54 3 个月前
题解
P1023
代码解释 :
-
输入处理:读取输入数据,包括预期价格、成本价、各价格点的销量,以及超过最高价后的销量递减量。
-
生成价格点:通过线性插值和递减处理生成所有可能的价格点及其销量。
-
约束条件分析:对于每个价格点,计算其总利润,并建立关于税金或补贴的约束条件,确保预期价格下的总利润最大。
-
求解最优解:通过分析约束条件,确定税金或补贴的可能范围,并找到绝对值最小的解。
AC Code :
CPP#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <climits>
using namespace std;
int main() {
// 读取输入
int p0;
cin >> p0;
int c, s_c;
cin >> c >> s_c;
vector<pair<int, int>> price_list = {{c, s_c}};
while (true) {
int p, s;
cin >> p >> s;
if (p == -1 && s == -1) break;
price_list.push_back({p, s});
}
int k;
cin >> k;
// 按价格排序
sort(price_list.begin(), price_list.end());
// 填充中间价格
vector<pair<int, int>> filled_prices;
for (size_t i = 0; i < price_list.size(); ++i) {
int p_current = price_list[i].first;
int s_current = price_list[i].second;
filled_prices.push_back({p_current, s_current});
if (i < price_list.size() - 1) {
int p_next = price_list[i + 1].first;
int s_next = price_list[i + 1].second;
int delta_p = p_next - p_current;
int delta_s = s_next - s_current;
if (delta_p > 1) {
int step = delta_s / delta_p;
for (int p = p_current + 1; p < p_next; ++p) {
int s = s_current + step * (p - p_current);
filled_prices.push_back({p, s});
}
}
}
}
// 处理超过最高价后的价格点
if (!price_list.empty()) {
int max_p = price_list.back().first;
int max_s = price_list.back().second;
int current_p = max_p + 1;
int current_s = max_s - k * (current_p - max_p);
while (current_s > 0) {
filled_prices.push_back({current_p, current_s});
current_p++;
current_s = max_s - k * (current_p - max_p);
}
}
// 确保filled_prices按价格排序并去重
sort(filled_prices.begin(), filled_prices.end());
map<int, int> price_dict;
for (const auto& ps : filled_prices) {
if (price_dict.find(ps.first) == price_dict.end()) {
price_dict[ps.first] = ps.second;
}
}
filled_prices.clear();
for (const auto& ps : price_dict) {
filled_prices.push_back(ps);
}
sort(filled_prices.begin(), filled_prices.end());
// 检查p0是否在filled_prices中,如果不在则计算其销量
int s0 = -1;
if (price_dict.find(p0) != price_dict.end()) {
s0 = price_dict[p0];
} else {
if (p0 < c) {
cout << "NO SOLUTION" << endl;
return 0;
}
if (filled_prices.empty()) {
cout << "NO SOLUTION" << endl;
return 0;
}
int max_p_filled = filled_prices.back().first;
int max_s_filled = filled_prices.back().second;
if (p0 > max_p_filled) {
int s_p0 = max_s_filled - k * (p0 - max_p_filled);
if (s_p0 < 0) s_p0 = 0;
filled_prices.push_back({p0, s_p0});
sort(filled_prices.begin(), filled_prices.end());
price_dict[p0] = s_p0;
s0 = s_p0;
} else {
bool found = false;
for (size_t i = 0; i < filled_prices.size() - 1; ++i) {
int p_prev = filled_prices[i].first;
int s_prev = filled_prices[i].second;
int p_next = filled_prices[i + 1].first;
int s_next = filled_prices[i + 1].second;
if (p_prev <= p0 && p0 <= p_next) {
if (p_prev == p0) {
s0 = s_prev;
found = true;
break;
}
if (p_next == p0) {
s0 = s_next;
found = true;
break;
}
int delta_p = p_next - p_prev;
int delta_s = s_next - s_prev;
int step = delta_s / delta_p;
int s_p = s_prev + step * (p0 - p_prev);
filled_prices.push_back({p0, s_p});
sort(filled_prices.begin(), filled_prices.end());
price_dict[p0] = s_p;
s0 = s_p;
found = true;
break;
}
}
if (!found) {
cout << "NO SOLUTION" << endl;
return 0;
}
}
}
// 处理每个p的条件
double low = -INFINITY;
double high = INFINITY;
for (const auto& ps : filled_prices) {
int p = ps.first;
int s_p = ps.second;
if (p == p0) continue;
if (s_p == s0) {
if (p0 >= p) continue;
else {
cout << "NO SOLUTION" << endl;
return 0;
}
} else {
double rhs = (p0 - c) * s0 - (p - c) * s_p;
double denominator = s_p - s0;
if (denominator > 0) {
double upper = rhs / denominator;
if (upper < high) high = upper;
} else {
double lower = rhs / denominator;
if (lower > low) low = lower;
}
// 检查是否已经无解
if (low > high) {
cout << "NO SOLUTION" << endl;
return 0;
}
}
}
// 计算t的整数解范围
int t_min = ceil(low);
int t_max = floor(high);
if (t_min > t_max) {
cout << "NO SOLUTION" << endl;
return 0;
}
// 寻找绝对值最小的t
int best_t;
if (t_min <= 0 && 0 <= t_max) {
best_t = 0;
} else {
// 比较两端点的绝对值
int abs_t_min = abs(t_min);
int abs_t_max = abs(t_max);
if (abs_t_min < abs_t_max) {
best_t = t_min;
} else if (abs_t_min > abs_t_max) {
best_t = t_max;
} else {
// 如果有正负绝对值相同的情况,取正数
best_t = max(t_min, t_max);
}
}
cout << best_t << endl;
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...