首页 > 代码库 > AC日记——国王游戏 洛谷 P1080
AC日记——国王游戏 洛谷 P1080
国王游戏
思路:
贪心+高精;
代码:
#include <bits/stdc++.h>using namespace std;#define maxn 1005struct DataType { int a,b,key; bool operator<(const DataType pos)const { return key<pos.key; }};struct DataType ai[maxn];struct BintType { int len; char ch[5000]; BintType operator*(const int pos)const { int i,p=0; BintType res; res.mem(); for(i=0;i<len;i++) { p+=(ch[i]-‘0‘)*pos; res.ch[i]=p%10+‘0‘,p/=10; } while(p) { res.ch[i]=p%10+‘0‘; p/=10,i++; } res.len=strlen(res.ch); return res; } BintType operator/(const int pos)const { BintType res; res.mem(); int i,p=0; for(i=len-1;i>=0;i--) { p=p*10+ch[i]-‘0‘; res.ch[i]=p/pos+‘0‘; p%=pos; } res.len=strlen(res.ch); for(int i=res.len-1;i>=0&&res.ch[i]==‘0‘;i--,res.len--); return res; } bool operator<(const BintType pos)const { if(len<pos.len) return true; else if(len>pos.len) return false; int i=len-1; while(i>=0&&ch[i]==pos.ch[i]) i--; if(i<0) return false; if(ch[i]<=pos.ch[i]) return true; else return false; } void mem() { memset(ch,0,sizeof(ch)),len=0; } void print() { for(int i=len-1;i>=0;i--) putchar(ch[i]); }};struct BintType ans,pos,temp;int n;inline void in(int &now){ char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}int main(){ in(n); for(int i=0;i<=n;i++)in(ai[i].a),in(ai[i].b),ai[i].key=ai[i].a*ai[i].b; sort(ai+1,ai+n+1); ans.ch[0]=‘0‘,ans.len=1; pos.ch[0]=‘1‘,pos.len=1; for(int i=0;i<=n;i++) { temp=pos/ai[i].b; if(ans<temp) ans=temp; pos=pos*ai[i].a; } ans.print(); return 0;}
AC日记——国王游戏 洛谷 P1080
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。