洛谷 P1080 国王游戏
程序员文章站
2023-11-13 13:32:58
[TOC] 题目 "P1080 国王游戏" 思路 贪心+高精度。按$a \times b$从小到大排序就可以了、 $Code$ cpp include define MAXN 1001 define rr register using namespace std; const int Big_B = ......
目录
题目
思路
贪心+高精度。按$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[]) {;}
上一篇: 谈析:高级网络运营有哪些分类
下一篇: 浅谈:地方门户网站如何赚到第一笔钱