题意：
一共N个人坐在坐在圆桌旁，服务员拿来了M份菜单。第i个人阅读菜单并点出自己喜欢的菜需要花费时间T[i]。 当一个人点完菜之后，就会把菜单传到他右手边的第一个人。 M份菜单是同时发出的，每个菜单只能同时被一个人阅读。 希望知道如何分发菜单，才能让点餐的总时间花费最少呢？
n<=5e4,m<=3e3
分析：
1.求的是最小值，考虑二分。
2.圆桌说明是环，处理环的方法：复制序列+枚举断点
所以：二分一个答案mid，check的时候枚举以每一个点作为开头，依次向后传菜单能否满足mid（依次向后传，时间超了就菜单++）
那么总复杂度为n*n*logn
考虑优化：
1.真的需要枚举每一个点做开头吗？
eg：1 3 2 6 7 明显，如果mid=7，那么应该这样划分：1 3 2 / 6 / 7
然后会发现，枚举从1开始，和从4开始，从5开始，是等价的划分方法。
所以说，只需要划分到前缀和刚好大于mid的位置2，就足够了
2.每一次传菜单的时候一定要一个一个传吗？
我们希望快速找到一个位置，刚好传到它就超时了，那么可以通过二分找这个位置：记录前缀和，lower_bound确定位置
最后复杂度：n*logn*logn
#include<bits/stdc++.h> using namespace std; #define N 50005 int n,m,a[N],sum[N*2],bn; bool work(int now,int x,int nx) { int cnt=0; while(now<=nx){ int pos=upper_bound(sum+1,sum+n*2,sum[now-1]+x)-sum;//优化2 if(now==pos) pos++; cnt++; now=pos; if(cnt>m) return false; } return true; } bool check(int x) { int xx=lower_bound(sum+1,sum+n*2,x)-sum;//优化1 for(int i=1;i<=xx;i++){ if(work(i,x,n+i-1)) return true; } return false; } int main() { freopen("dinner.in","r",stdin); freopen("dinner.out","w",stdout); int maxn=0,minn=0,ans=0; scanf("%d%d",&n,&m); bn=n; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); minn=max(a[i],minn); maxn+=a[i]; sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++) sum[n+i-1]=sum[n]+sum[i-1]; int l=minn,r=maxn; while(l<r){ int mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid; else l=mid+1; } printf("%d ",ans); } /* 4 2 1 2 3 4 ans 5 3 2 1 5 10 */