题目分析

题目答案不具有单调性，所以不可以二分，转而思考贪心。因为无法确定位置，所以考虑如何才能让对于每一个$1 ~ i$使得$i$的答案最大，即$1 ~ i$最后一个最优。若设对于位置$i$，$a[i]$表示左手，$b[i]$表示右手，$S$为其前面所有人的左手之积，那么他的答案就是$\frac{S}{b[i]}$，如果存在在$i$后边的$j$的答案更优，即$\frac{S * a[i]}{b[j]} > \frac{S * a[j]}{b[i]} => a[i] * b[i] > a[j] * b[j]$，这样只要我们以a[i] * b[i]为关键字从小到大排序，就能保证每个前缀的最后一个都是最优的，只要$o(n)$扫一遍取最大值即可，记得使用高精度。

code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int N = ;

int n, a[N], b[N], c[N], ka, kb, kc;

inline int read(){

    int i = , f = ; char ch = getchar();

    for(; (ch < '' || ch > '') && ch != '-'; ch = getchar());

    if(ch == '-') f = -, ch = getchar();

    for(; ch >= '' && ch <= ''; ch = getchar())

        i = (i << ) + (i << ) + (ch - '');

    return i * f;

}

inline void wr(int x){

    if(x < ) putchar('-'), x = -x;

    if(x > ) wr(x / );

    putchar(x %  + '');

}

struct bign{

    int len, s[];

    bign():len(){memset(s, , sizeof s);}

    bign(int x):len(){

        memset(s, , sizeof s);

        while(x){

            s[++len] = x % ;

            x /= ;

        }

        if(!len) len = ;

    }

    inline void clear(){

        while(len >  && s[len] == ) len--;

    }

    inline bign operator * (const bign &b) const{

        bign ret;

        ret.len = len + b.len + ;

        for(int i = ; i <= len; i++)

            for(int j = ; j <= b.len; j++)

                ret.s[i + j - ] += s[i] * b.s[j];

        for(int i = ; i <= ret.len; i++)

            if(ret.s[i] >= ){

                ret.s[i + ] += ret.s[i] / ;

                ret.s[i] %= ;

            }

        ret.clear();

        return ret;

    }

    inline bign operator - (const bign &b) const{

        bign ret;

        ret.len = len;

        for(int i = ; i <= len; i++){

            ret.s[i] = ret.s[i] + s[i];

            if(i <= b.len) ret.s[i] = ret.s[i] - b.s[i];

            if(ret.s[i] < ){

                ret.s[i + ]--;

                ret.s[i] += ;

            }

        }

        ret.clear();

        return ret;

    }

    bign operator / (int b) {

        bign c;

        int f = ;

        for(int i = len; i >= ; i--){

            f = f *  + s[i];

            while(!(f < b)){

                f -= b;

                c.s[i]++;

            }

        }

        c.len = len;

        c.clear();

        return c;

    }

    inline bool operator > (const bign &b) const{

        if(len != b.len) return len > b.len;

        for(int i = len; i >= ; i--)

            if(s[i] != b.s[i]) return s[i] > b.s[i];

        return false;

    }

    inline bool operator == (const bign &b) const{

        if(len != b.len) return false;

        for(int i = len; i >= ; i--)

            if(s[i] != b.s[i]) return false;

        return true;

    }

    inline bool operator < (const bign &b) const{

        if(len != b.len) return len < b.len;

        for(int i = len; i >= ; i--)

            if(s[i] != b.s[i]) return s[i] < b.s[i];

        return false;

    }

    inline void print(){

        for(int i = len; i >= ; i--)

            wr(s[i]);

    }

}fa, ans, big0, big10;

struct node{

    int a, b, c;

    inline bool operator < (const node &u) const{

        if(c != u.c) return c < u.c;

        return b > u.b;

    }

}data[N];

int main(){

    n = read(), ka = read(), kb = read();

    for(int i = ; i<= n; i++){

        data[i].a = read(), data[i].b = read();

        data[i].c = data[i].a * data[i].b;

    }

    sort(data + , data + n + );

    fa = ka;

    ans = ;

    bign tmpa, t;

    for(int i = ; i <= n; i++){

        tmpa = data[i].a;

        t = fa / data[i].b;

        if(t > ans) ans = t;

        fa = fa * tmpa;

    }

    ans.print();

    return ;

}

巴特西

【NOIP2012提高组】国王游戏贪心 + 高精度

题目分析

code

最新文章

热门文章

巴特西

【NOIP2012提高组】国王游戏 贪心 + 高精度

题目分析

code

最新文章

热门文章

【NOIP2012提高组】国王游戏贪心 + 高精度