只有八十分,第八个点和第九个点过不了,不知道为什么,代码应该蛮清楚了,有没有大哥帮我看看的……
#include <bits/stdc++.h>
using namespace std;
#define SAME 1
#define LARGER 2
#define SMALLER 3
#define ONE 1
#define JQ 1000000
// inline int read() //编译的时间会多一点,但是运行的时间会小一些
// {
// int x = 0, y = 1;
// char c = getchar(); // y代表正负(1.-1),最后乘上x就可以了。
// while (c < '0' || c > '9')
// {
// if (c == '-')
// {
// y = -1;
// }
// c = getchar();
// } //如果c是负号就把y赋为-1
// while (c >= '0' && c <= '9')
// {
// x = x * 10 + c - '0', c = getchar();
// }
// return x * y; //乘起来输出
// }
/*
本题需要解决的问题:
①如何进行排序的问题
②如何进行乘法的数据存储的问题
③如何进行除法的数据存储的问题
④如何进行数据的比较和最大值实时更新的问题
*/
inline void write(int x)
{
//我们是1000000进制的
//最多的时候,是一个6位数
if (x < 10)
{
printf("00000%d", x);
}
else if (x < 100)
{
printf("0000%d", x);
}
else if (x < 1000)
{
printf("000%d", x);
}
else if (x < 10000)
{
printf("00%d", x);
}
else if (x < 100000)
{
printf("0%d", x);
}
else
{
printf("%d", x);
}
}
typedef struct node
{
int l, r;
} Minister;
bool cmp(Minister a, Minister b)
{
return (a.l * a.r) < (b.l * b.r);
}
//思想:高精度的乘法,不一定是要用10进制的,可以是114514进制,
//是多少进制都是可以的,只要在int范围之内就好了
// 为了很好的输出,最好还是10的整数次方为单位,这比较好
void times(int d, int *a)
{
//给它乘上一个d
//我们就用a[0]表示有几位吧,这样就不需要m了!
a[a[0] + 1] = 0;
a[a[0] + 2] = 0;
for (int i = 1; i <= a[0]; i++)
{
a[i] *= d;
}
for (int i = 1; i <= a[0]; i++)
{
a[i + 1] += a[i] / 1000000;
a[i] %= 1000000;
}
if (a[a[0] + 1] != 0)
{
a[0]++;
}
a[a[0] + 2] = 0;
// a是一个倒着存储的,表示一个大的数字的值的数组,这个数组是1000000进制的
//不要作死!不然等会输出的时候,会难受死你!
// 倒着存储:倒了,但是不完全倒了
}
//倒着存储的
int which_one_is_bigger(int *a, int *b)
{
if (a[0] > b[0])
{
return LARGER;
}
if (a[0] < b[0])
{
return SMALLER;
}
for (int i = a[0]; i >= 1; i--)
{
if (a[i] > b[i])
{
return LARGER;
}
else if (a[i] < b[i])
{
return SMALLER;
}
}
return SAME;
}
//比较两个数组的大小,两个数组是逆着存储的,数组的第一位表示一共有多少位
//排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数
// 3 1 1 2 3 4 5 6 7
void division(int *a, int d, int *answer)
{
// int r = yushu;
// 最终的答案是正着存储的?
// printf("除法进行正常");
int r = 0;
answer[a[0] + 1] = 0;
answer[a[0] + 2] = 0;
// printf("除法进行正常");
for (int i = a[0]; i >= 1; i--)
{
answer[i] = ((r * JQ) + a[i]) / d;
r = ((r * JQ) + a[i]) % d;
}
// printf("除法进行正常");
int the_first_not_zero = 0;
for (int j = a[0]; j >= 1; j--)
{
if (answer[j] != 0)
{
the_first_not_zero = j;
break;
}
}
answer[0] = the_first_not_zero;
answer[answer[0] + 1] = 0;
answer[answer[0] + 2] = 0;
return;
}
void print_(int *a)
{
printf("%d", a[a[0]]);
for (int i = a[0] - 1; i >= 1; i--)
{
write(a[i]);
// printf("");
}
printf("\n");
return;
}
int main()
{
// int maxx[100];
// int a[100000]; // a表示的是当前这么多个数字做乘法之后得到的值
int the_max_answer[9999];
int temp_answer[9999];
int times_result[9999];
//这个东西指的是maxx的最大值
int n;
the_max_answer[0] = 1;
the_max_answer[1] = 0;
the_max_answer[2] = 0;
temp_answer[0] = 1;
temp_answer[1] = 0;
temp_answer[2] = 0;
scanf("%d", &n);
int king_l, king_r;
scanf("%d%d", &king_l, &king_r);
Minister minister[1010];
times_result[0] = 1; //国王的左手一位
times_result[1] = king_l;
// printf("\n现在国王左手的数字是: ");
// print_(times_result);
// scanf("%d", &n);
// the_max_answer[0] = 0;
// the_max_answer[1] = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &minister[i].l, &minister[i].r);
}
// printf("\n完成了输入\n");
sort(minister + 1, minister + n + 1, cmp);
// printf("\n完成了排序\n");
for (int i = 1; i <= n; i++)
{
//一共有n个大臣,现在开始不断地乘除,看看最大值是啥情况。
// times(minister[i].l, times_result);
// printf("下面是第 %d 个乘积\n", i);
// print_(times_result);
// printf("\n");
// printf("第 %d 个乘积\n", i);
division(times_result, minister[i].r, temp_answer);
// printf("第 %d 次除法进行正常\n", i); //除法出问题了??
if (which_one_is_bigger(temp_answer, the_max_answer) == LARGER)
{
for (int i = 1; i <= temp_answer[0]; i++)
{
the_max_answer[i] = temp_answer[i];
}
the_max_answer[0] = temp_answer[0];
the_max_answer[the_max_answer[0] + 1] = 0;
the_max_answer[the_max_answer[0] + 2] = 0;
}
times(minister[i].l, times_result);
}
// printf("进行到这里了!\n");
// printf("\n最大的答案的a[0]是: %d\n", the_max_answer[0]);
if (the_max_answer[0] >= 99999999)
{
printf("_");
return 0;
}
print_(the_max_answer);
// write(123);
return 0;
}