CF1063D Candies for Children

客官°小女子只卖身不卖艺 2022-01-12 10:51 139阅读 0赞

[CF1063D Candies for Children][CF1063D_Candies for Children]

分类讨论题

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<bits/stdc++.h>
    #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<<endl
    #define pii pair<int,int>
    using namespace std;
    #define int long long 
    typedef long long ll;
    template<class T>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<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>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 "<<i<<" "<<M<<endl;
        ll ret=-1;
        if(i==0){
            ll p=M;
            if(p<=len) ret=max(ret,p+n-len);
            p=M+1;
            if(p>=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 "<<ret<<endl;
        return ret;
    }
    int main(){
        rd(n);rd(l);rd(r);rd(k);
        if(l<=r) len=r-l+1;
        else len=n-l+1+r;
        // cout<<" len "<<len<<endl;
        if(n<=2e6){
            ll ans=0;
            for(ans=n;ans>=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*
    */

转载于:https://www.cnblogs.com/Miracevin/p/10870823.html

[CF1063D_Candies for Children]: https://www.luogu.org/problemnew/show/CF1063D