求助,70分TLE,贪心+高精
查看原帖
求助,70分TLE,贪心+高精
515071
WWW_DP_COM_CN楼主2025/8/29 17:22

TLE:第7,8,9个数据点

#include <bits/stdc++.h>
#define O 10005
using namespace std;
int n;
string Left = "1",maxx = "0",Right;	//表示所有人的左手乘积 
struct minister
{
	long long a,b;
}	lst[O];
bool cmp_minister(minister m1,minister m2)
{
	return m1.a * m1.b < m2.a * m2.b;
}
bool cmp(string a,string b)
{
	if(a.size() == b.size())
	{
		for(long long i = 0;i < a.size();++i)
		{
			if(a[i] != b[i])
				return a[i] < b[i];
		}
	}
	return a.size() < b.size();
}
string fuc_str(int num)
{
	string str;
	while(num)
	{
		str = char(num % 10 + '0') + str;
		num /= 10; 
	}
	return str;
}
string my_plus(string a,string b)
{
	if(cmp(a,b))
		swap(a,b);
	string c;
	long long m = 0;
	for(long long i = 1;i <= b.size();++i)
	{
		long long q = a[a.size() - i] + b[b.size() - i] - 2 * '0' + m;
		m = 0;
		if(q >= 10)
			m = 1,q -= 10;
		c = char(q + '0') + c;	
	}
	for(long long i = a.size() - b.size() - 1;i >= 0;--i)
	{
		long long q = a[i] + m - '0';
		m = 0;
		if(q >= 10)
			m = 1,q -= 10;
		c = char(q + '0') + c;
	}
	if(m)
		c = '1' + c;
	return c;
}
string my_time(string a,int b)
{
	string sum = "0";
	int zero = 0;
	//表示一共加几个0在答案后面 
	for(int i = a.size() - 1;i >= 0;--i)
	{
		int num = a[i] - '0';
		//表示当前数
		int x = num * b;
		string q = fuc_str(x);
		for(int k = 1;k <= zero;++k)
			q += '0';
		sum = my_plus(q,sum); 
		++zero;
	}
	string final;
    long long idx = 0;
	while(sum[idx] == '0' && idx < sum.size() - 1)
		++idx;
	for(long long i = idx;i < sum.size();++i)
		final += sum[i];
	return final;
}
string my_divide(string a,int b)
{
    long long lst1[O],lst2[O],jin = 0;
    for (long long i = 0;i < a.size();i++)
        lst1[i + 1] = a[i] - '0';
    for (long long i = 1;i <= a.size();i++)
    {
    	long long num = jin * 10 + lst1[i];
        lst2[i] = num / b;
        jin = num % b;
    }
    long long idx = 1;
    while(lst2[idx] == 0 && idx < a.size())
        idx++;
    string ans = "";
    for (long long i = idx;i <= a.size();i++) 
		ans += char(lst2[i] + '0');
	return ans;
}
signed  main()
{
	scanf("%d",&n);
	cin >> Left >> Right;
	for(long long i = 1;i <= n;++i)
		scanf("%d %d",&lst[i].a,&lst[i].b);
	sort(lst + 1,lst + 1 + n,cmp_minister);
	for(long long i = 1;i <= n;++i)
	{
		string coin;
		coin = my_divide(Left,lst[i].b);
		if(cmp(maxx,coin))
			maxx = coin;
		Left = my_time(Left,lst[i].a);
	}
	cout << maxx;
	return 0;
}
/*
10
5 7
4 2
7 3
7 2
4 4
1 7
5 3
6 1
4 5
2 3
3 7
ans:134400
*/
2025/8/29 17:22
加载中...