馕

题目译自 JOISC 2019 Day1 T3「ナン / Naan」

JOI咖喱店以提供很长（？）的馕而闻名。它提供的馕有L种口味，编号从1到L。「JOI特色馕」是店内最受欢迎的一道菜。馕的总长度为L厘米。我们定义「点X」为馕上距离馕左端X厘米处的点。对于 $1 \le j \le L$ ，点j-1和点j间的一段馕是第j种口味的。
有N个人来到了JOI咖喱店，他们每个人的偏好都不同，具体的说，第i个人每吃一厘米的风味j的馕，就会获得 $V_{i,j}$ 的快乐度。
他们只买了一个JOI特色馕，他们将用下面的方式分享馕：

选择N-1个分数 $X_1, \ldots ,X_{N-1}$ ，满足 $0\lt X_1\lt X_2\lt \ldots \lt X_{N-1}\lt L$ 。
选择N的一个排列 $P_1, \ldots P_N$ 。
对于每一个 $k(1 \le k \le N-1)$ ，在点 $X_k$ 的位置切一刀，然后馕将被切成N个部分。
第 $k(1 \le k \le N)$ 个部分的左端点为 $X_{k-1}$ ，右端点为 $X_{k}$ ，这里我们认为 $X_0=0,X_N=L$ 。
第 $P_i$ 个人将吃掉第i个部分。

现在他们想公平的分配馕，他们认为一种分配方法是公平的，当且仅当每个人获得的快乐度都不小于他们独吞整个馕所获得的快乐度的 $\frac{1}{N}$ 。

现在给你N个人的信息，你需要判断是否存在一种公平的分配方式，如果存在，输出一组分配方案。

输出数据到标准输出中。
如果无解，输出一行-1；
如果有解，首先输出N-1行，第i行两个整数 $A_i,B_i$ ，要求 $A_i,B_i$ 是一对满足 $X_i= \frac{A_i}{B_i}(1 \le i \le N)$ 的整数对。
接下来一行N个整数，第i个数表示 $P_i$ 。
你的输出需要满足：

$1 \le B_i \le 10^9(1 \le i \le N)$ 。

$0\lt \frac{A_1}{B_1}\lt \frac{A_2}{B_2}\lt ...\lt \frac{A_{N-1}}{B_{N-1}}\lt L$ 。

$P_1,...,P_N$ 是一个1,...,N的排列。第i个人获得的总快乐度不小于 $\frac{V_{i,1}+V_{i,2}+...+V_{i,L}}{N}(1 \le i \le N)$ 。

$A_i,B_i$ 不必互质。

可以证明，如果输入数据有解，那么一定存在一组满足上述条件的解。

#include <cstdio> #include <algorithm> #define ll long long using namespace std;const int Q=1<<11;struct dt{ll u,w;dt(){}dt(ll a,ll b){u=a,w=b;}void P(){printf("%lld %lld\n",u,w);}}s[Q][Q];bool operator<(dt a,dt b){return (long double)a.u*b.w<(long double)b.u*a.w;}ll f[Q];int b[Q],o[Q];int main(){int n,l;scanf("%d%d",&n,&l);for(int p=1;p<=n;p++){for(int i=1;i<=l;i++)scanf("%lld",&f[i]),f[i]+=f[i-1];for(int h=0,i=1;i<=n;i++){while(f[h+1]*n<f[l]*i)++h;ll p2=1LL*n*(f[h+1]-f[h]),p1=1LL*h*p2+f[l]*i-f[h]*n,g=__gcd(p1,p2);s[p][i]=dt(p1/g,p2/g);}}for(int i=1;i<=n;i++){int x=0;for(int j=1;j<=n;j++)if((!o[j])&&((!x)||s[j][i]<s[x][i]))x=j;o[x]=1;b[i]=x;}for(int i=1;i<n;i++)s[b[i]][i].P();for(int i=1;i<=n;i++)printf("%d ",b[i]);}

详情