我也不知道是什么的贪心.

Description

给定$L, R$. 定义一个数字的性质$p$值为去掉所有后缀$0$后长度$\times2$, 如果结尾为$5$, 则减$1$. 问$[L,R]$中$p$值最小的数字是谁. 如有多个取最小.

Solution

一个贪心思路是一定多取0, 所以对于一个结尾有$0$的数字, 下一个可能的位置一定是加上$10^{c}$, $c$是$0$的个数.

这样我们就可以加速枚举了.

还是记一下思路吧.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    int mn = 0x3f3f3f3f; int ans, l, r;
    scanf("%d%d", &l, &r);
    while (l <= r) {
      int zr = 0, tmp = l, pw = 1;
      while (!(tmp % 10)) tmp /= 10, zr++, pw *= 10;
      int tmp2 = tmp, len = 0, lst = tmp % 10;
      while (tmp2) tmp2 /= 10, len++;
      int p = ((lst == 5) ? 2 * len - 1 : 2 * len);
      if (p < mn) mn = p, ans = l;
      l += pw;
    }
    printf("%d\n", ans);
  }
  return 0;
}