题解 - 定价

题目

题目描述

你如此计算一个价格 \(p\)（为正整数）的荒谬程度：

1. 首先将 \(p\) 看做一个由数字组成的字符串（不带前导 \(0\)）；
2. 然后，如果 \(p\) 的最后一个字符是 \(0\)，就去掉它。重复这一过程，直到 \(p\) 的最后一个字符不是 \(0\)；
3. 记 \(p\) 的长度为 \(a\)，如果此时 \(p\) 的最后一位是 \(5\)，则荒谬程度为 \(2a - 1\)；否则为 \(2a\)。

现在，你要出售一样闲置物品，你能接受的定价在 \([L, R]\) 范围内，如果荒谬度最低的价格不唯一，输出最小的那个。

思路简析

我去这题难受死我了。

不是很难细节贼多。

但是考虑暴力：
对于本题的要求是尽可能多的后导零。
设当前数为 \(x\)，有 \(l\) 个后导零，显然 \((x, x+10^x)\) 中没有优于 \(x\) 的价格。
所以可以不一个一个搜而是 \(10^x\) 个 \(10^x\) 个搜。

而且当 \(x\) 改变的时候 \(10^x\) 也改变，所以每次（或者进行一个优化：每 \(10\) 次）都要重新统计后导零。

CODE

Time complexity:\(O(Unknown)\)

#include <bits/stdc++.h>
namespace {
#define fiin(x) freopen(x".in", "r", stdin)
#define fiout(x) freopen(x".out", "w", stdout)
#define files(x) fiin(x), fiout(x)
using namespace std;
#define ll long long
#define db double
const int man = 2.5e5;
}

int T, a, b, mnp = 1e9+10, res;
void ger (int) ;
int main () {
#ifndef ONLINE_JUDGE
    files("test");
#endif
    scanf ("%d", &T);
    while (T --) {
        scanf("%d%d", &a, &b);
        while (a <= b) {
            int la = a, cnt = 0, lx = 0;
            while (!(la%10)) la /= 10, ++ cnt;
            int f = la%10;
            for (int i = la; i; i /= 10) ++ lx;
            int p = -(f == 5)+2*lx;
            if (mnp > p) mnp = p, res = a;
            a += pow(10, cnt);
        } printf("%d\n", res);
        mnp = 1e9+10;
    } return 0;
}