分类讨论题

n<=1e11，

整体上先分n<=2e6与否讨论

len长度，ans贪心的人，p就是len这一段贪心的人

n<=2e6

枚举答案ans

要满足：

p>=0,

p>=ans-(n-len)

p<=ans,

p<=len

p+len=k mod (ans+n)=r

p=r-len

判断p是否合法即可

 

n>=2e6

枚举i

i*ans+p=k-i*n-len=M

观察，ans++，p-=i

p最小时候，ans最大

p最小是:M%i

考虑要满足的条件：

p>=0,p<=len,p<=ans

ans>=0,ans<=p+(n-len),ans<=n

先把ans调整到n以内，再调整到p+(n-len)以内

判断p是否合法即可

因为最大合法的ans一定是最优的，ans更小，p更大，本身答案更劣，而且也更可能不合法

 

至于最后一个取1个，但是是贪心的，

只需要k=k+1再做一遍，并且要求p>=1

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;#define int long long typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{ll n,l,r,k;ll len;ll che(ll i,ll M){ // cout<<" che "<
           <<" "<
            
             <
             
              =1&&p<=len) ret=max(ret,p+n-len); } else{ ll p=M%i; ll ans=(M-p)/i; if(ans>n) { p+=(ans-n)*i; ans=n; } if(ans>n-len+p){ ll tmp=(ans-(n-len+p)+i)/(i+1); ans-=tmp; p+=tmp*i; } if(p>=0&&p<=min(ans,len)) ret=max(ret,ans); p=(M+1)%i; ans=(M+1-p)/i; if(ans>n){ p+=(ans-n)*i; ans=n; } if(ans>n-len+p){ ll tmp=(ans-(n-len+p)+i)/(i+1); ans-=tmp; p+=tmp*i; } if(p>=1&&p<=min(ans,len)) ret=max(ret,ans); } // cout<<" ret "<
              
               <
               
                =0;--ans){ ll r=k%(ans+n); if(r==0) r+=ans+n; int p=r-len; if(p>=max((ll)0,ans-(n-len))&&p<=min(ans,len)) break; r=(k+1)%(ans+n); p=r-len; if(p>=max((ll)1,ans-(n-len))&&p<=min(ans,len)) break; } if(ans>=0) printf("%lld",ans); else printf("-1"); }else{ ll M=k-len; ll ans=-1; for(ll i=0;M>=0;++i,M-=n){ ll ret=che(i,M); ans=max(ans,ret); } printf("%lld",ans); } return 0;} }signed main(){ Miracle::main(); return 0;}/* Author: *Miracle**/