题解：CF2093B Expensive Number

洛谷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}

后所有的数位。

CPP

#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;
    }
}

题解：CF2093B Expensive Number

文章操作

简要题意

思路

相关推荐

评论

题解：CF2093B Expensive Number