CF258A Little Elephant and Bits 题解

思路

一道很简单的贪心题。

先观察样例，可以发现，答案都是删除了原数的第一个 \(0\)。

我们试着来证明一下这样是最优的。

对于删除一位，也就是等同于让该位之前的所有数字都向后移了一位，也就是它们在十进制下表示的数就会减少。为了让减少的数字最少，那么删掉的这个数要尽量靠前。而且，显然删除 \(0\) 一定优于删除 \(1\)。综上，删除原数从头开始第一个 \(0\) 便是正确答案。

如果你交上一份直接删除第一个 \(0\) 的代码，你就会 WA，因为，如果输入是 111111111111，你就会原样输出。因此，如果扫描到了最后一位还是没有找到 \(0\)，则随意删除一位。

代码

#include
#include
using namespace std;

int main() {
	string str;
	cin >> str;
	bool del = false; //是否删除了一个0
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '0') {
			str.erase(i, 1); //删除该位
			del = true; //标记
			break;
		}
	}
	if (!del) { //没有删除过0
		str.erase(0, 1); //随意删除一位
	}
	cout << str << endl;
	return 0;
}