【LOJ】#3032. 「JOISC 2019 Day1」馕

待我称王封你为后i 2021-11-01 13:44 197阅读 0赞

# LOJ\#3032. 「JOISC 2019 Day1」馕 #

处理出每个人把馕切成N段，每一段快乐度相同，我们选择第一个排在最前的人分给他的第一段，然后再在未选取的的人中选一个第二个排在最前的切一下，并把第二段给他，这样下去一定有解

代码细节具体在比较大小的时候成绩可能需要int128

然后在给每个人分段的时候，把一个馕的长度当成\\(Nq\\)，把要得到的每段长度当成\\(sum\\)(所有段快乐度的总和)就可以1去分了

#include <bits/stdc++.h>
    #define fi first
    #define se second
    #define pii pair<int,int>
    #define mp make_pair
    #define pb push_back
    #define space putchar(' ')
    #define enter putchar('\n')
    #define eps 1e-10
    #define MAXN 2005
    #define ba 47
    //#define ivorysi
    using namespace std;
    typedef long long int64;
    typedef unsigned int u32;
    typedef double db;
    template<class T>
    void read(T &res) {
        res = 0;T f = 1;char c = getchar();
        while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
        }
        while(c >= '0' && c <= '9') {
        res = res * 10 +c - '0';
        c = getchar();
        }
        res *= f;
    }
    template<class T>
    void out(T x) {
        if(x < 0) {x = -x;putchar('-');}
        if(x >= 10) {
        out(x / 10);
        }
        putchar('0' + x % 10);
    }
    int64 gcd(int64 a,int64 b) {
        return b == 0 ? a : gcd(b,a % b);
    }
    struct factor {
        int64 x,y;
        factor(int64 a = 0,int64 b = 1) {
        x = a;y = b;
        int64 g = gcd(x,y);x /= g;y /= g;
        }
        friend factor operator + (const factor &a,const factor &b) {
        int64 u = a.x * b.y + b.x * a.y,d = a.y * b.y;
        int64 g = gcd(u,d);u /= g;d /= g;
        return factor(u,d);
        }
        friend factor operator - (const factor &a,const factor &b) {
        int64 u = a.x * b.y - a.y * b.x;
        int64 d = a.y * b.y;
        int64 g = gcd(u,d);u /= g;d /= g;
        return factor(u,d);
        }
        friend factor operator * (const factor &a,const factor &b) {
        int64 u = a.x * b.x,d = a.y * b.y;
        int64 g = gcd(u,d);
        u /= g;d /= g;
        return factor(u,d);
        }
        friend factor operator / (const factor &a,const factor &b) {
        int64 u = a.x * b.y,d = a.y * b.x;
        int64 g = gcd(u,d);u /= g;d /= g;
        return factor(u,d);
        }
        friend bool operator < (const factor &a,const factor &b) {
        return (__int128)a.x * b.y < (__int128)a.y * b.x;
        }
        friend bool operator == (const factor &a,const factor &b) {
        return a.x * b.y == a.y * b.x;
        }
        friend bool operator <= (const factor &a,const factor &b) {
        return a < b || a == b;
        }
    }cut[MAXN],poi[MAXN][MAXN];
    int N,L,p[MAXN];
    int64 rem[MAXN],v[MAXN][MAXN],sum[MAXN];
    bool vis[MAXN];
    void Solve() {
        read(N);read(L);
        for(int i = 1 ; i <= N ; ++i) {
        for(int j = 1 ; j <= L ; ++j) {
            read(v[i][j]);
            sum[i] = sum[i] + v[i][j];
        }
        }
        for(int i = 1 ; i <= N ; ++i) {
        int now = 1;
        for(int j = 1 ; j <= L ; ++j) rem[j] = N * v[i][j];
        for(int j = 1 ; j < N ; ++j) {
            int64 sv = sum[i];
            while(1) {
            if(rem[now] < sv) {sv -= rem[now];++now;continue;}
            else {
                rem[now] -= sv;
                poi[i][j] = now - factor(rem[now],N * v[i][now]);
                break;
            }
            }
        }
        }
        for(int j = 1 ; j < N ; ++j) {
        int pos = -1;
        for(int i = 1 ; i <= N ; ++i) {
            if(!vis[i]) {
            if(pos == -1) pos = i;
            else if(poi[i][j] < poi[pos][j]) pos = i;
            }
        }
        p[j] = pos;vis[pos] = 1;
        out(poi[pos][j].x);space;out(poi[pos][j].y);enter;
        }
        for(int i = 1 ; i <= N ; ++i) {
        if(!vis[i]) {p[N] = i;break;}
        }
        for(int i = 1 ; i <= N ; ++i) {
        out(p[i]);space;
        }
        enter;
    }
    int main() {
    #ifdef ivorysi
        freopen("03-02.in","r",stdin);
    #endif
        Solve();
    }

转载于:https://www.cnblogs.com/ivorysi/p/10953256.html