第一样例下载样例后没问题,但交上去就不对了,还有3个TLE,求助大佬
查看原帖
第一样例下载样例后没问题,但交上去就不对了,还有3个TLE,求助大佬
227279
tranxray楼主2023/9/6 18:29
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
int n;
string a, b;

int comparestr(string str1, string str2) {
	if (str1.length() > str2.length()) return 1;
	else if (str1.length() < str2.length()) return -1;
	else return str1.compare(str2);
}

string add(string str1, string str2) {
	string str;
	int len1 = str1.length();
	int len2 = str2.length();
	if (len1 < len2) {
		for (int i = 0; i < len2 - len1; i++)
			str1 = '0' + str1;
	}
	if (len2 < len1) {
		for (int i = 0; i < len1 - len2; i++)
			str2 = '0' + str2;
	}
	int len = str1.length();
	int cf = 0;
	int temp=0;
	for (int i = len - 1; i >= 0; i--) {
		temp = str1[i] - '0' + str2[i] - '0' + cf;
		cf = temp / 10;
		str = char(temp % 10 + '0') + str;
	}
	if (cf != 0)str = char(cf + '0') + str;
	return str;
}

string sub(string str1, string str2) {
	string str;
	int tmp = str1.length() - str2.length();
	int cf = 0;
	for (int i = str2.length() - 1; i >= 0; i--) {
		if (str1[tmp + i] < str2[i] + cf) {
			str = char(str1[tmp + i] - str2[i] - cf + '0' + 10) + str;
			cf = 1;
		}
		else {
			str = char(str1[tmp + i] - str2[i] - cf + '0') + str;
			cf = 0;
		}
	}
	for (int i = tmp - 1; i >= 0; i--) {
		if (str1[i] - cf >= '0') {
			str = char(str1[i] - cf) + str;
			cf = 0;
		}
		else {
			str = char(str1[i] - cf + 10) + str;
			cf = 1;
		}
	}
	str.erase(0, str.find_first_not_of('0'));
	return str;
}

string mul(string str1, string str2) {
	string str;
	int len1 = str1.length(), len2 = str2.length();
	string tmpstr;
	for (int i = len2 - 1; i >= 0; i--) {
		tmpstr = "";
		int tmp = str2[i] - '0';
		int t = 0, cf = 0;
		if (tmp == 0)continue;
		for (int j = len1 - 1; j >= 0; j--) {
			t = (tmp * (str1[j] - '0') + cf) % 10;
			cf = (tmp * (str1[j] - '0') + cf) / 10;
			tmpstr = char(t + '0') + tmpstr;
		}
		if (cf != 0) tmpstr = char(cf + '0') + tmpstr;
		for (int j = 0; j < len2 - 1 - i; j++)
			tmpstr = tmpstr + '0';
		str = add(str, tmpstr);
	}
	str.erase(0, str.find_first_not_of('0'));
	if (str.empty())str = "0";
	return str;
}

void div(string str1, string str2, string& quotient, string& residue) {
	quotient = residue = "";
	if (str2 == "0") {
		quotient = residue = "ERROR";
		return;
	}
	else if (str1 == "0") {
		quotient = residue = "0";
		return;
	}
	int res = comparestr(str1, str2);
	if (res < 0) {
		quotient = "0";
		residue = str1;
		return;
	}
	else if (res == 0) {
		quotient = "1";
		residue = "0";
		return;
	}
	int len1 = str1.length(), len2 = str2.length();
	string tmpstr;
	tmpstr.append(str1, 0, len2 - 1);
	for (int i = len2 - 1; i < len1; i++) {
		tmpstr = tmpstr + str1[i];
		tmpstr.erase(0, tmpstr.find_first_not_of('0'));
		if (tmpstr.empty())
			tmpstr = "0";
		for (char ch = '9'; ch >= '0'; ch--) {
			string str, tmp;
			str = str + ch;
			tmp = mul(str2, str);
			if (comparestr(tmp, tmpstr) <= 0) {
				quotient = quotient + ch;
				tmpstr = sub(tmpstr, tmp);
				break;
			}
		}
	}
	residue = tmpstr;
	quotient.erase(0, quotient.find_first_not_of('0'));
	if (quotient.empty()) quotient = "0";
	if (residue.empty()) residue = "0";
	return;
}

struct minister {
	string left;
	string right;
}m[1001];

bool cmp(const minister& m1, const minister& m2){
	if (comparestr(mul(m1.left, m1.right), mul(m2.left, m2.right)) >= 0)
		return false;
	else return true;
}

int main() {
	scanf("%d", &n);
	cin >> a >> b;
	for (int i = 0; i < n; i++) {
		cin >> m[i].left >> m[i].right;
	}
	sort(m, m + n,cmp);
	string max_num = "";
	string now_num = "",residue;
	string sum = a;
	for (int i = 0; i < n; i++) {
		div(sum, m[i].right, now_num, residue);
		if (comparestr(now_num, max_num) == 1)
			max_num = now_num;
		sum = mul(sum, m[i].left);
	}
	cout << max_num << endl;
	return 0;
}
2023/9/6 18:29
加载中...