【题解】洛谷 P1080 国王游戏
2019-10-08 08:48:26来源:博客园 阅读 ()
【题解】洛谷 P1080 国王游戏
目录
- 题目
- 思路
- $Code$
题目
P1080 国王游戏
思路
贪心+高精度。按$a \times b$从小到大排序就可以了、
$Code$
#include<bits/stdc++.h>
#define MAXN 1001
#define rr register
using namespace std;
const int Big_B = 10; const int Big_L = 1;
inline int intcmp_ (int a, int b) { if (a > b) return 1; return a < b ? -1 : 0; }
struct Int {
#define rg register
inline int max (int a, int b) { return a > b ? a : b; }
inline int min (int a, int b) { return a < b ? a : b; }
std :: vector <int> c; Int () {} typedef long long LL;
Int (int x) { for (; x > 0; c.push_back (x % Big_B), x /= Big_B); }
Int (LL x) { for (; x > 0; c.push_back (x % Big_B), x /= Big_B); }
inline void CrZ () { for (; !c.empty () && c.back () == 0; c.pop_back ()); }
inline Int &operator += (const Int &rhs){
c.resize (max (c.size (), rhs.c.size ())); rg int i, t = 0, S;
for (i = 0, S = rhs.c.size (); i < S; ++ i)
c[i] += rhs.c[i] + t, t = c[i] >= Big_B, c[i] -= Big_B & (-t);
for (i = rhs.c.size (), S = c.size (); t && i < S; ++ i)
c[i] += t, t = c[i] >= Big_B, c[i] -= Big_B & (-t);
if (t) c.push_back (t); return *this;
}
inline Int &operator -= (const Int &rhs){
c.resize (max (c.size (), rhs.c.size ())); rg int i, t = 0, S;
for (i = 0, S = rhs.c.size (); i < S; ++ i)
c[i] -= rhs.c[i] + t, t = c[i] < 0, c[i] += Big_B & (-t);
for (i = rhs.c.size (), S = c.size (); t && i < S; ++ i)
c[i] -= t, t = c[i] < 0, c[i] += Big_B & (-t);
CrZ (); return *this;
}
inline Int &operator *= (const Int &rhs){
rg int na = c.size (), i, j, S, ai;
c.resize (na + rhs.c.size ()); LL t;
for (i = na - 1; i >= 0; -- i){
ai = c[i], t = 0, c[i] = 0;
for (j = 0, S = rhs.c.size (); j < S; ++ j){
t += c[i + j] + (LL) ai * rhs.c[j];
c[i + j] = t % Big_B, t /= Big_B;
}
for (j = rhs.c.size (), S = c.size (); t != 0 && i + j < S; ++ j)
t += c[i + j], c[i + j] = t % Big_B, t /= Big_B;
assert (t == 0);
}
CrZ (); return *this;
}
inline Int &operator /= (const Int &rhs) { return *this = div (rhs); }
inline Int &operator %= (const Int &rhs) { return div (rhs), *this; }
inline Int &shlb (int l = 1){
if (c.empty ()) return *this; c.resize (c.size () + l);rg int i;
for (i = c.size () - 1; i >= l; -- i) c[i] = c[i - l];
for (i = 0; i < l; ++ i) c[i] = 0;
return *this;
}
inline Int &shrb (int l = 1){
for (rg int i = 0; i < c.size () - l; ++ i) c[i] = c[i + l];
c.resize (max (c.size () - l, 0)); return *this;
}
inline Int div (const Int &rhs){
assert (!rhs.c.empty ()); Int q, r; rg int i; if (rhs > *this) return 0;
q.c.resize (c.size () - rhs.c.size () + 1); rg int _l, _r, mid;
for (i = c.size () - 1; i > c.size () - rhs.c.size (); -- i) r.shlb (), r += c[i];
for (i = c.size () - rhs.c.size (); i >= 0; -- i){
r.shlb (); r += c[i];
if (r.Comp (rhs) < 0) q.c[i] = 0;
else {
_l = 0, _r = Big_B;
for (; _l != _r; ){
mid = _l + _r >> 1;
if ((rhs * mid).Comp (r) <= 0) _l = mid + 1; else _r = mid;
}
q.c[i] = _l - 1, r -= rhs * q.c[i];
}
}
q.CrZ (), *this = r; return q;
}
inline int Comp (const Int &rhs) const {
if (c.size () != rhs.c.size ()) return intcmp_ (c.size (), rhs.c.size ());
for (rg int i = c.size () - 1; i >= 0; -- i)
if (c[i] != rhs.c[i]) return intcmp_ (c[i], rhs.c[i]);
return 0;
}
friend inline Int operator + (const Int &lhs, const Int &rhs)
{ Int res = lhs; return res += rhs; }
inline friend Int operator - (const Int &lhs, const Int &rhs){
if (lhs < rhs){
putchar ('-');
Int res = rhs; return res -= lhs;
}
else { Int res = lhs; return res -= rhs; }
}
friend inline Int operator * (const Int &lhs, const Int &rhs)
{ Int res = lhs; return res *= rhs; }
friend inline Int operator / (const Int &lhs, const Int &rhs)
{ Int res = lhs; return res.div (rhs); }
friend inline Int operator % (const Int &lhs, const Int &rhs)
{ Int res = lhs; return res.div (rhs), res; }
friend inline std :: ostream &operator << (std :: ostream &out, const Int &rhs){
if (rhs.c.size () == 0) out << "0";
else {
out << rhs.c.back ();
for (rg int i = rhs.c.size () - 2; i >= 0; -- i)
out << std :: setfill ('0') << std :: setw (Big_L) << rhs.c[i];
}
return out;
}
friend inline std :: istream &operator >> (std :: istream &in, Int &rhs){
static char s[100000];
in >> s + 1; int Len = strlen (s + 1);
int v = 0; LL r = 0, p = 1;
for (rg int i = Len; i >= 1; -- i){
++ v; r = r + (s[i] - '0') * p, p *= 10;
if (v == Big_L) rhs.c.push_back (r), r = 0, v = 0, p = 1;
}
if (v != 0) rhs.c.push_back (r); return in;
}
friend inline bool operator < (const Int &lhs, const Int &rhs)
{ return lhs.Comp (rhs) < 0; }
friend inline bool operator <= (const Int &lhs, const Int &rhs)
{ return lhs.Comp (rhs) <= 0; }
friend inline bool operator > (const Int &lhs, const Int &rhs)
{ return lhs.Comp (rhs) > 0; }
friend inline bool operator >= (const Int &lhs, const Int &rhs)
{ return lhs.Comp (rhs) >= 0; }
friend inline bool operator == (const Int &lhs, const Int &rhs)
{ return lhs.Comp (rhs) == 0; }
friend inline bool operator != (const Int &lhs, const Int &rhs)
{ return lhs.Comp (rhs) != 0; }
#undef rg
};
struct qwq {
Int a,b,cj;
}qaq[MAXN];
bool cmp(qwq x,qwq y) {
return x.cj<y.cj;
}
int Main (){
int n;
cin>>n;
cin>>qaq[0].a>>qaq[0].b;
for(rr int i=1;i<=n;++i) {
cin>>qaq[i].a;
cin>>qaq[i].b;
qaq[i].cj=qaq[i].a*qaq[i].b;
}
sort(qaq+1,qaq+n+1,cmp);
Int maxx=0,flag=1;
for(rr int i=1;i<=n;++i) {
flag*=qaq[i-1].a;
maxx=max(maxx,flag/qaq[i].b);
}
cout<<maxx;
return 0;
}
int ZlycerQan = Main ();
int main (int argc, char *argv[]) {;}
原文链接:https://www.cnblogs.com/poi-bolg-poi/p/11623430.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C++分治策略实现快速排序
下一篇:长乐国庆集训Day1
- Unsolved --> Solved OJ思路题解 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- 洛谷P1907口算练习题 2020-03-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash