题解：CF2093B Expensive Number

NEKO_Daze · 2025-04-19 19:27:39 · 题解

洛谷CF2093B || CodeForces 2093 B

简要题意

定义一个数 n=\overline{a_1a_2\cdots a_k} 的花费为 \frac{\overline{a_1a_2\cdots a_k}}{a_1+a_2+\cdots+a_k}。对其进行若干次操作，每次操作删除其中一位数，求使其花费最小的最少操作数。最多删除 k-1 个数位且最后得到的数必须大于 0。

思路

当只有一个非 0 数位，即 n=\overline{a} >0 时，花费为 \frac{a}{a}=1，容易证得此为最小花费。因此对于所有数，最小花费一定为 1。我们只需要在此基础上保留不影响该花费的数位，以最小化操作数。

我们选取最后一个非零数位 a_{end} 为分界点，对两边的数进行分类讨论：

• 当 i < end 时，若 a_i 不为 0，保留后花费必然增加，所以必须删除。在删除所有不为 0 的数后，所有前面的 0 变为前导零，并不会增加花费，不必删除。
• 当 i>end 时，所有数都是 0，每有一个 0 就会使分子变大，而分母不变，因此也必须删除。

综上，我们删除 a_{end} 前所有不为 0 的数位，删除 a_{end} 后所有的数位。

#include <bits/stdc++.h>
using namespace std;
int t;
string s;
int main()
{
    cin >>t;
    while (t--)
    {
        cin >> s;
        int cnt = 0, end = s.length() - 1;
        for (int i = s.length() - 1; i >= 0; i--)
        {
            if (s[i] != '0') {end=i;break;}
        }
        for (int i = 0; i < s.length(); i++)
        {
            if (i==end) continue;
            if (s[i] != '0' && i < end) cnt++;
            if (s[i] == '0' && i > end) cnt++;
        }
        cout << cnt << endl;
    }
}