BZOJ4029 [HEOI2015] 定价策略优化（贪心算法）

题目描述

本题来源于 BZOJ 和 洛谷，在给定的价格区间内找到一个最优价格，使得该价格在进行特定操作后达到最小化的目标。

解决方案

该问题的核心在于利用贪心算法，每次对当前价格增加其十进制表示下的最低有效位（lowbit），从而逐步逼近最优解。具体实现如下：

#include 
#include 
using namespace std;

inline int read() {
    int x = 0; bool t = false; char ch = getchar();
    while ((ch <'0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') t = true, ch = getchar();
    while (ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
    return t ? -x : x;
}

int lowbit(int x) {
    for (int i = 1;; i *= 10)
        if (x % 10) return i;
        else x /= 10;
}

int calc(int x) {
    while (x % 10 == 0) x /= 10;
    int l = 0;
    if (x % 10 == 5) l -= 1;
    while (x) l += 2, x /= 10;
    return l;
}

int main() {
    int T = read();
    while (T--) {
        int l = read(), r = read(), ans = 1e9, val = l;
        while (l <= r) {
            int x = calc(l);
            if (ans > x) ans = x, val = l;
            l += lowbit(l);
        }
        printf("%d\n", val);
    }
    return 0;
}

上述代码首先读取输入数据，然后通过循环遍历每个可能的价格，并计算其经过特定操作后的值。最终输出最优价格。