专栏文章

题解:P1023 [NOIP 2000 普及组] 税收与补贴问题

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

文章操作

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

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

题解

P1023


代码解释 :

  1. 输入处理:读取输入数据,包括预期价格、成本价、各价格点的销量,以及超过最高价后的销量递减量。
  2. 生成价格点:通过线性插值和递减处理生成所有可能的价格点及其销量。
  3. 约束条件分析:对于每个价格点,计算其总利润,并建立关于税金或补贴的约束条件,确保预期价格下的总利润最大。
  4. 求解最优解:通过分析约束条件,确定税金或补贴的可能范围,并找到绝对值最小的解。

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 条评论,欢迎与作者交流。

正在加载评论...