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();
}