[Luogu] 国王游戏
2024-09-05 07:16:24
https://www.luogu.org/problemnew/show/P1080
按照 a * b 排序
高精度
#include <bits/stdc++.h> using namespace std;
const int N = ; #define LL long long int n, ak, bk;
struct Node {
int A, B, AB;
bool operator <(const Node a) const{return AB < a.AB;}
} G[N]; #define gc getchar() LL sum, Answer = ; inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c < '') x = x * + c - '', c = gc;
return x;
} int main() {
n = read(); ak = read(); bk = read();
for(int i = ; i <= n; i ++) G[i].A = read(), G[i].B = read(), G[i].AB = G[i].A * G[i].B;
sort(G + , G + n + );
sum = ak;
for(int i = ; i <= n; i ++) {
LL imp = sum / G[i].B;
if(!imp) imp = ;
Answer = max(Answer, imp);
sum *= G[i].A;
}
if(Answer == ) Answer = ;
cout << Answer;
return ;
}
/*
3
1 1
2 3
7 4
4 6
*/
#include <bits/stdc++.h> using namespace std; int now[],sum[],ans[],add[]; struct Node {
int a;
int b;
long long a_b;
} node[]; int read() {
int ans = , flag = ;
char ch = getchar();
while( (ch > '' || ch < '') && ch != '-' ) ch = getchar();
if(ch == '-') flag = -, ch = getchar();
while(ch >= '' && ch <= '') ans = ans * + ch - '', ch = getchar();
return ans * flag;
}
void times(int x) {
memset(add, , sizeof(add));
for(int i = ; i <= ans[]; i ++) {
ans[i] = ans[i] * x;
add[i+] += ans[i] / ;
ans[i] %= ;
}
for(int i = ; i <= ans[] + ; i ++) {
ans[i] += add[i];
if(ans[i]>=) {
ans[i+]+=ans[i]/;
ans[i]%=;
}
if(ans[i]!=) {
ans[]=max(ans[],i);
}
}
return ;
}
int divition(int x) {
memset(add,,sizeof(add));
int q=;
for(int i=ans[]; i>=; i--) {
q*=;
q+=ans[i];
add[i]=q/x;
if(add[]== && add[i]!=) {
add[]=i;
}
q%=x;
}
return ;
}
bool compare() {
if(sum[]==add[]) {
for(int i=add[]; i>=; i--) {
if(add[i]>sum[i]) return ;
if(add[i]<sum[i]) return ;
}
}
if(add[]>sum[]) return ;
if(add[]<sum[]) return ;
}
void cp () {
memset(sum,,sizeof(sum));
for(int i=add[]; i>=; i--) {
sum[i]=add[i];
}
return ;
}
bool cmp(Node a,Node b) {
return a.a_b<b.a_b;
}
int main() {
int n=read();
for(int i=; i<=n; i++) {
node[i].a=read(),node[i].b=read();
node[i].a_b=node[i].a*node[i].b;
}
sort(node+,node+n+,cmp);
ans[]=,ans[]=;
for(int i=; i<=n; i++) {
times(node[i-].a);
divition(node[i].b);
if(compare()) {
cp();
}
}
for(int i=sum[]; i>=; i--)
printf("%d",sum[i]);
return ;
}
最新文章
- Android自定义控件之基本原理
- flush和reflush
- linux 持续构建(自动部署) 重启动tomcat或进程的脚本
- jquery 实现重复点击一个元素时不重复执行效果
- Bitmap简单操作笔记
- 密码校验正则表达式(java 环境)
- Spring AOP(注解方式)
- mysql zip 版本配置方法
- Groovy 在eclipse中的使用
- Learning Scrapy笔记(三)- Scrapy基础
- Redis集群
- IDEA中运行KafkaWordCount程序
- python类定义
- react native 子组件向父组件传值
- Consul常用命令
- netbeans增加yii的代码提示
- SUPERSOCKET 客户端
- 20165308 预备作业3 Linux安装及学习
- Anaconda详细安装使用教程
- es6基础(1)--声明