牛客 ZT13 小红的数字删除

牛客 ZT13 小红的数字删除

1. 3的倍数的特征是：一个数的各个数位上的数相加的和如果是3的倍数，则这个数也一定是3的倍数
2. 用map存储每个数位对3求余的余数
   • 对3求余等于0，说明都是三的倍数，min(m[0], n - 1)，要保证每次删除后，该整数都是3的倍数且大于0
   • 对3求余等于1：
     • 第一个数位必须删除
       • 如果第一位删除后，前置0也需要跟着删除
       • 而且所有数位不能全部删除
     • 第一个数位非必要删除，min(m[0] + 1, n - 1)
     • 第一次操作不能进行输出0
   • 对3求余等于2：
     • 第一个数位必须删除
       • 如果第一位删除后，前置0也需要跟着删除
       • 而且所有数位不能全部删除
     • 第一个数位非必要删除，min(m[0] + 1, n - 1)
     • 第一次操作不能进行输出0

代码如下：

#include<bits/stdc++.h>
using namespace std;
//如果剩下来全是3的倍数
int main() {
	int t;
	cin >> t;
	while (t--) {
		string ch;
		cin >> ch;

		map<int, int>m;
		int sum = 0;
		for (int i = 0; i < ch.size(); i++) {
			m[(ch[i] - '0') % 3]++;
			sum += ( ch[i] - '0');
		}
		int n = ch.size();
		//都是3的倍数，不能全部删除
		if (sum % 3 == 0) {
			cout << min(m[0], n - 1) << endl;
		} else if (sum % 3 == 1) {
			if (m[1]) {
				//必须删第一个数字
				int si = 0;
				//si是第一个数位删除后，需要同时删除的前置0
				if (m[1] == 1 && ((ch[0] - '0') % 3 == 1)) {
					int f = 0;
					for (int i = 1; i < ch.size(); i++) {
						if (ch[i] == '0' ) {
							si++;

						} else break;
					}
					if (si == m[0] && si)
						cout << 0 << endl;
					else {
						if (m[0] + 1 == n) {//如果第一个数位删了，后面数位都是3的倍数，不能全部删除
							//1+m[0]-si-1
							cout << m[0] - si << endl;
							//TODO
						} else
							cout << 1 + m[0] - si << endl;
					}

				} else
					cout << min(m[0] + 1, n - 1) << endl;
			} else cout << 0 << endl;
		} else {
			if (m[2]) {
				//	cout<<"***"<<endl;
				int si = 0;
				if (m[2] == 1 && ((ch[0] - '0') % 3 == 2)) {
					for (int i = 1; i < ch.size(); i++) {
						if (ch[i] == '0' ) {
							si++;
						} else break;
					}
					//全删了
					if (si == m[0] && si)
						cout << 0 << endl;
					else {
						if (m[0] + 1 == n) {
							cout << m[0] - si << endl;
							//TODO
						} else
							cout << 1 + m[0] - si << endl;
					}
				} else
					cout << min(m[0] + 1, n - 1) << endl;
			} else cout << 0 << endl;
		}
	}
}