// 洛谷P1080国王游戏
// 作者: 仟濹 CSDN账号
// 此题需要用到 "高精度算法"
// 数据范围:
// 大臣人数 - n --> 1 ~ 10000
// 国王、大臣左右手正数范围 a, b --> 1 ~ 10000
// 在通过计算以后,int 以及 long long 会存不开,所以使用 【高精度整数】存储计算的后的结果
// 要想让计算的结果小一些,就要按照
// 变量:
// num - 大臣人数
// data[] - 大臣的左右手数值 --> data[].a - 左手数值; data[].b - 右手数值
#include <iostream>
#include <algorithm>
using namespace std;
struct ddd{
long long a;
long long b;
};
// 存储 结果 使用高精度
struct hugeint{
long long nums[ 100000 ] = { 0, 1 };
int len = 1;
}ans;
// 高精度 * 单精度
void mul( long long num );
// 高精度 / 单精度 --> 最后一位大臣的金钱百分百最多,所以计算最后一位大臣的金币就可以了
void div( long long num );
// 比较函数
bool cmp( ddd a, ddd b );
int main( void ){
int num; // 总大臣数量
cin >> num;
ddd data[ 100005 ]; // king 与 大臣的左右手数据 - 大臣数量 1 ~ 1000, 防止越界 1005
// 输入国王左右手的数据
cin >> data[ 0 ].a >> data[ 0 ].b;
// 输入大臣的 左右手数值
for ( int i = 1; i <= num; i ++ ){
cin >> data[ i ].a >> data[ i ].b;
}
sort( data + 1, data + num + 1, cmp);
// 计算所有大臣的乘积
for( int i = 0; i < num; i ++ ){
mul( data[ i ].a ); // nums * 大臣左手
}
// // 测试
// for( int i = ans.len; i >= 1; i -- ){
// cout << ans.nums[ i ];
// }
// cout << " " << data[ num ].b << endl;
// 最后一个大臣前面的所有左手乘积 / 最后一个大臣右手
div( data[ num ].b );
for( int i = ans.len; i >= 1; i -- ){
cout << ans.nums[ i ];
}
// // 测试
// mul( 1 );
// for( int i = ans.len; i >= 1; i -- ){
// cout << ans.nums[ i ];
// }
return 0;
}
// 比较函数 --> data[ i ].a * data[ i ].b < data[ i + 1 ].a * data[ i + 1 ].a
bool cmp( ddd num1, ddd num2 ){
return num1.a * num1.b < num2.a * num2.b;
}
void mul(long long num) {
// 处理进位
long long carry = 0; // 进位
for (int i = 1; i <= ans.len; i++) {
long long temp = ans.nums[i] * num + carry; // 当前位乘积加上进位
ans.nums[i] = temp % 10; // 当前位结果
carry = temp / 10; // 进位
}
// 处理多余进位
while (carry > 0) {
ans.len++; // 长度加1
ans.nums[ans.len] = carry % 10; // 取余数
carry /= 10; // 处理进位
}
}
void div( long long num ){
hugeint s1 = ans;
for ( int i = ans.len; i >= 1; i -- ){
ans.nums[ i ] = s1.nums[ i ] / num;
s1.nums[ i - 1 ] += s1.nums[ i ] % num * 10;
}
while( ans.nums[ ans.len ] == 0 && ans.len > 1 ){
ans.len --;
}
// 如果 ? / num == 0.** 为了向下取整,应为1
if( ans.len == 0 ){
ans.len ++;
ans.nums[ 1 ] = 1;
}
}// 洛谷P1080国王游戏
// 作者: 仟濹 CSDN账号
// 此题需要用到 "高精度算法"
// 数据范围:
// 大臣人数 - n --> 1 ~ 10000
// 国王、大臣左右手正数范围 a, b --> 1 ~ 10000
// 在通过计算以后,int 以及 long long 会存不开,所以使用 【高精度整数】存储计算的后的结果
// 要想让计算的结果小一些,就要按照
// 变量:
// num - 大臣人数
// data[] - 大臣的左右手数值 --> data[].a - 左手数值; data[].b - 右手数值
#include <iostream>
#include <algorithm>
using namespace std;
struct ddd{
long long a;
long long b;
};
// 存储 结果 使用高精度
struct hugeint{
long long nums[ 100000 ] = { 0, 1 };
int len = 1;
}ans;
// 高精度 * 单精度
void mul( long long num );
// 高精度 / 单精度 --> 最后一位大臣的金钱百分百最多,所以计算最后一位大臣的金币就可以了
void div( long long num );
// 比较函数
bool cmp( ddd a, ddd b );
int main( void ){
int num; // 总大臣数量
cin >> num;
ddd data[ 100005 ]; // king 与 大臣的左右手数据 - 大臣数量 1 ~ 1000, 防止越界 1005
// 输入国王左右手的数据
cin >> data[ 0 ].a >> data[ 0 ].b;
// 输入大臣的 左右手数值
for ( int i = 1; i <= num; i ++ ){
cin >> data[ i ].a >> data[ i ].b;
}
sort( data + 1, data + num + 1, cmp);
// 计算所有大臣的乘积
for( int i = 0; i < num; i ++ ){
mul( data[ i ].a ); // nums * 大臣左手
}
// // 测试
// for( int i = ans.len; i >= 1; i -- ){
// cout << ans.nums[ i ];
// }
// cout << " " << data[ num ].b << endl;
// 最后一个大臣前面的所有左手乘积 / 最后一个大臣右手
div( data[ num ].b );
for( int i = ans.len; i >= 1; i -- ){
cout << ans.nums[ i ];
}
// // 测试
// mul( 1 );
// for( int i = ans.len; i >= 1; i -- ){
// cout << ans.nums[ i ];
// }
return 0;
}
// 比较函数 --> data[ i ].a * data[ i ].b < data[ i + 1 ].a * data[ i + 1 ].a
bool cmp( ddd num1, ddd num2 ){
return num1.a * num1.b < num2.a * num2.b;
}
void mul(long long num) {
// 处理进位
long long carry = 0; // 进位
for (int i = 1; i <= ans.len; i++) {
long long temp = ans.nums[i] * num + carry; // 当前位乘积加上进位
ans.nums[i] = temp % 10; // 当前位结果
carry = temp / 10; // 进位
}
// 处理多余进位
while (carry > 0) {
ans.len++; // 长度加1
ans.nums[ans.len] = carry % 10; // 取余数
carry /= 10; // 处理进位
}
}
void div( long long num ){
hugeint s1 = ans;
for ( int i = ans.len; i >= 1; i -- ){
ans.nums[ i ] = s1.nums[ i ] / num;
s1.nums[ i - 1 ] += s1.nums[ i ] % num * 10;
}
while( ans.nums[ ans.len ] == 0 && ans.len > 1 ){
ans.len --;
}
// 如果 ? / num == 0.** 为了向下取整,应为1
if( ans.len == 0 ){
ans.len ++;
ans.nums[ 1 ] = 1;
}
}
哪位大佬可以指点一下,太感谢了