[loj3032]馕

（直接贪心会导致分子和分母过大）

令$S_{i}=\sum_{j=1}^{L}V_{i,j}$（即其独吞整个馕的快乐度），对第$i$个人求出$n$个位置$x_{1},x_{2},...,x_{n-1}$，使得以此划分出的$n$段中，其吃每一段的快乐度都恰为$\frac{S_{i}}{n}$

假设$j-1<x_{i}\le j$，那么$(j-x_{i})V_{j}=\sum_{k=1}^{j}V_{i}-\frac{i}{n}S$，即可得到$x_{i}$的分子和分母的范围分别为$2\times 10^{8}$和$4\times 10^{11}$，都可以存储

$x_{i}=j+\frac{\frac{i}{n}S-\sum_{k=1}^{j}V_{i}}{V_{j}}$

接下来，对于答案的$x_{i}$（从小到大枚举$i$），选择未选择的人中$x_{i}$的最小值以及对应的人即可

关于这一做法的正确性，考虑这个人的$x_{i-1}$必然不小于答案的$x_{i-1}$（否则应该选其），即成立

（分数比较时，分子乘分母的范围为$8\times 10^{19}$，可以使用__int128）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 2005

 4 #define ll long long

 5 #define LL __int128

 6 LL mul(ll x,ll y){

 7     return (LL)x*y;

 8 }

 9 struct Frac{

10     ll x,y;

11     bool operator < (const Frac &k)const{

12         return mul(x,k.y)<mul(y,k.x);

13     }

14     Frac operator + (const Frac &k)const{

15         return Frac{x*k.y+y*k.x,y*k.y};

16     }

17     Frac operator * (const Frac &k)const{

18         return Frac{x*k.x,y*k.y};

19     }

20 }x[N][N];

21 int n,m,a[N][N],sum[N][N],vis[N],ans[N];

22 int main(){

23     scanf("%d%d",&n,&m);

24     for(int i=1;i<=n;i++)

25         for(int j=1;j<=m;j++){

26             scanf("%d",&a[i][j]);

27             sum[i][j]=sum[i][j-1]+a[i][j];

28         }

29     for(int i=1;i<=n;i++)

30         for(int j=1,k=1;j<n;j++){

31             while (Frac{sum[i][k],1}<Frac{1LL*j*sum[i][m],n})k++;

32             x[i][j]=Frac{k,1}+(Frac{1LL*j*sum[i][m],n}+Frac{-sum[i][k],1})*Frac{1,a[i][k]};

33         }

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

35         int k=0;

36         for(int j=1;j<=n;j++)

37             if ((!vis[j])&&((!k)||(x[j][i]<x[k][i])))k=j;

38         vis[k]=1,ans[i]=k;

39         if (i<n)printf("%lld %lld\n",x[k][i].x,x[k][i].y);

40     }

41     for(int i=1;i<=n;i++)printf("%d ",ans[i]);

42 }

巴特西

[loj3032]馕

最新文章

热门文章