{"id":1285,"date":"2024-01-21T19:37:09","date_gmt":"2024-01-21T11:37:09","guid":{"rendered":"http:\/\/www.forillusion.com\/?p=1285"},"modified":"2025-02-14T11:39:10","modified_gmt":"2025-02-14T03:39:10","slug":"basic-algorithms-training50-3-binary-cut","status":"publish","type":"post","link":"https:\/\/www.forillusion.com\/index.php\/basic-algorithms-training50-3-binary-cut\/","title":{"rendered":"\u7b97\u6cd5\u57fa\u7840\u8bad\u7ec3 50 \u9898\uff08\u4e09\uff09\u4e8c\u5206"},"content":{"rendered":"\n

<\/div><\/p>\n\n\n\n

#JC0301. Angry Cows<\/h2>\n\n\n\n

\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n

\u5229\u7528\u4e8c\u5206\uff0c\u6765\u67e5\u627e\u8ddd\u79bb\u503c\uff0c\u901a\u8fc7\u5224\u65ad\u8be5\u8ddd\u79bb\u503c\u662f\u5426\u80fd\u5b89\u6392\u7684\u4e0b\u6240\u6709\u7684\u725b\u6765\u8c03\u6574l\u548cr\u3002<\/p>\n\n\n\n

int n,m,a[100005];\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI n>>m;\n    F(i,1,n)\n        CI a[i];\n    sort(a+1,a+n+1);\n\n    int l=0,r=a[n]-a[1],mid;\n    while (l<=r)\n    {\n        \n        mid=(r+l)\/2;\n        int x=a[1]+mid,t=2,s=1;\n        while (t<=n)\n        {\n            if(a[t]>=x) x=a[t]+mid,s++;\n            t++;\n        }\n        if (s>=m) l=mid+1;\n        else r=mid-1;\n    }\n\n    CO l-1 L;\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0302. Best Cow Fences<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u5229\u7528\u4e8c\u5206\uff0c\u67e5\u627e\u5e73\u5747\u6570\uff0c\u5e76\u5224\u65ad\u662f\u5426\u5b58\u5728\u957f\u5ea6\u4e0d\u4f4e\u4e8eL\u7684\u5b50\u4e32\u80fd\u8fbe\u5230\u8be5\u5e73\u5747\u6570\u5e73\u5747\u6570\u3002l\u7684\u521d\u59cb\u4e4b\u4e3a-1e6\uff0cr\u7684\u521d\u59cb\u503c\u4e3a1e6\u3002\u8ba1\u7b97\u51fa\u4e2d\u95f4\u503cm\u540e\uff0c\u5c06Ai\u4e2d\u7684\u6bcf\u4e00\u4e2a\u6570\u51cf\u53bbm\uff0c\u5927\u4e8e\u5e73\u5747\u503cm\u7684\u6570\u7ed3\u679c\u4e3a\u6b63\uff0c\u5c0f\u4e8e\u5e73\u5747\u503cm\u7684\u6570\u7ed3\u679c\u4e3a\u8d1f\uff1b\u7136\u540e\u518d\u8ba1\u7b97\u4e00\u4e2a\u524d\u7f00\u548c\u6570\u7ec4d\uff0c\u6c42\u6700\u5927\u7684\u5e73\u5747\u503c\uff0c\u9700\u8981\u627e\u5230\u524d\u7f00\u548cd\u4e2d\u6700\u5c11\u7684\u4e00\u4e2a\u548c\u6700\u5927\u7684\u503c\uff0c\u5e76\u4fdd\u8bc1\u6700\u5927\u7684\u503c\u5728\u6700\u5c0f\u7684\u503c\u53f3\u8fb9\uff0c\u4e14\u76f8\u8ddd\u5927\u4e8eL\u3002<\/p>\n\n\n\n
int n,ll,a[100005];\ndouble b[100005],d[100005];\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI n>>ll;\n    F(i,1,n)\n        CI a[i];\n    \n    double l=-1e6,r=1e6,m;\n    while (r-l>1e-5)\n    {\n        m=(l+r)\/2;\n\n        F(i,1,n)\n            b[i]=a[i]-m;\n\n        F(i,1,n)\n            d[i]=b[i]+d[i-1];\n\n        \n        double minl=1e10,avg=-1e10;\n        F(i,ll,n)\n        {\n            minl=min(minl,d[i-ll]);\n            avg=max(avg,d[i]-minl);\n        }\n\n        if (avg>=0) l=m;\n        else r=m;\n    }\n\n    CO int(r*1000) L;\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0304. Chat Ban<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u5229\u7528\u4e8c\u5206\uff0c\u627e\u5230\u80fd\u53d1\u7684\u540e\u4e00\u6761\u6d88\u606f\uff0cl\u548cr\u5b58\u50a8\u53d1\u4fe1\u606f\u7684\u6761\u6570\uff0c\u5982\u679cm\u5c0f\u4e8ek\uff0c\u5219\u7528\u6c42\u548c\u516c\u5f0fm*(m+1)\/2\u7b97\u51fa\u53d1\u9001\u7684\u6807\u7b7e\u6570\uff0c\u5982\u679c\u5927\u4e8ek\uff0c\u5219\u7528\u6c42\u548c\u516c\u5f0f\u7b97\u51fa\u672a\u53d1\u51fa\u7684\u8868\u60c5\u6570\uff0c\u5e76\u7528\u603b\u6570\u51cf\u53bb\u672a\u53d1\u51fa\u7684\u8868\u60c5\u6570\uff0c\u5f97\u5230\u5df2\u53d1\u7684\u8868\u60c5\u6570\uff1ak*k-(2*k-1-m)*(2*k-1-m+1)\/2<\/p>\n\n\n\n
LL t,k,x;\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI t;\n    while (t--)\n    {\n        CI k>>x;\n        if (k*k<=x)\n            CO 2*k-1 L;\n        else\n        {\n            LL l=0,r=2*k-1;\n            while (l<r)\n            {\n                LL m=(l+r)\/2;\n                LL s=0;\n                if (m<=k) s=m*(m+1)\/2;\n                else s=k*k-(2*k-1-m)*(2*k-1-m+1)\/2;\n                if (s>=x) r=m;\n                else l=m+1;\n            }\n            CO r L;\n        }\n\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0305. Cow Acrobats<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u5229\u7528\u8d2a\u5fc3\uff0c\u5148\u5c06\u6570\u7ec4\u6309\u7167w+s\u503c\u6392\u5e8f\uff0c\u7136\u540e\u518d\u6c42\u51fa\u524d\u7f00\u548c\u5e76\u5229\u7528\u524d\u7f00\u548c\u548c\u6c42\u51fa\u5371\u9669\u503c\u7684\u6700\u5927\u503c\u3002<\/p>\n\n\n\n
struct cow\n{\n    LL w,s;\n} a[50001];\nLL n,ans=-0x3f3f3f,s[500001];\n\nbool cmp(cow a,cow b)\n{\n    return a.w+a.s>b.w+b.s;\n}\n\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI n;\n    F(i,1,n)\n        CI a[i].w>>a[i].s;\n    sort(a+1,a+n+1,cmp);\n    F(i,1,n)\n        s[i]=s[i-1]+a[i].w;\n    F(i,1,n)\n    {\n        LL t=s[n]-s[i];\n        t=t-a[i].s;\n        ans=max(ans,t);\n    }\n    CO ans L;\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0306. Fly<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u6700\u8282\u7701\u7684\u65b9\u6cd5\u4fbf\u662f\u6700\u540e\u7740\u9646\u540e\u7528\u5b8c\u5168\u90e8\u7684\u71c3\u6599\uff0c\u4e8e\u662f\u53ef\u4ee5\u5012\u6c42\u51fa\u7740\u9646\u9700\u8981\u7684\u71c3\u6599\u503c\uff0c\u4e0d\u65ad\u5012\u6c42\u51fa\u71c3\u6599\u503c\uff0c\u5f97\u5230\u6700\u5c0f\u7684\u53d1\u5c04\u71c3\u6599\u91cf\u3002\u5982\u679c\u4e00\u4e2a\u71c3\u6599\u53ea\u80fd\u8d77\u98de\u6216\u7740\u96461\u5428\u7684\u706b\u7bad\uff0c\u5219\u6c38\u8fdc\u65e0\u6cd5\u4f7f\u706b\u7bad\u8d77\u98de\u6216\u7740\u9646\u3002<\/p>\n\n\n\n
int n;\ndouble p,ans,m,a[10001],b[10001];\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI n>>m;\n    int f=1;\n    F(i,0,n-1)\n    {\n        CI a[i];\n        if (a[i]==1) f=0;\n    }\n    F(i,0,n-1)\n    {\n        CI b[i];\n        if (b[i]==1) f=0;\n    }\n\n    ans=m;\n    if (f)\n    {\n        FD(i,n-1,0)\n        {\n            p=ans*1.0\/(b[(i+1)%n]-1);\n            ans+=p;\n            p=ans*1.0\/(a[i]-1);\n            ans+=p;\n        }\n        CO fixed << setprecision(6)<< ans-m L;\n        \/\/ printf(\"%lf\\n\",ans-m);\n    }\n    else \n    {\n        CO -1 L;\n        \/\/ printf(\"-1\\n\");\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0307. Hamburgers<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u5229\u7528\u6570\u5b66\u5173\u7cfb\u786c\u7b97\u5373\u53ef\u3002<\/p>\n\n\n\n
LL n[3],p[3],r,ans,t[3],z[3],am,m;\nstring s;\n\nLL z3()\n{\n    m=min(z[0],min(z[1],z[2]));\n    ans+=m;\n    F(i,0,2)\n        n[i]-=m*t[i];\n}\n\nLL z2()\n{\n    m=0x7fffffffffffffff;\n    int o;\n    F(i,0,2)\n        if (z[i]) m=min(m,z[i]);\n        else o=i;\n    \n\n    if ((t[o]-n[o])*p[o]<=r)\n    {\n        r-=(t[o]-n[o])*p[o];\n        ans++;\n        m--;\n        F(i,0,2)\n            n[i]-=t[i];\n        n[o]=0;\n\n        m=min(m,r\/(t[o]*p[o]));\n        ans+=m;\n        r-=m*t[o]*p[o];\n        \n        F(i,0,2)\n            if (z[i]) n[i]-=m*t[i];\n    }\n}\n\nLL z1()\n{\n    m=0;\n    int o1=0,o2=0,y;\n    F(i,0,2)\n        if (z[i]) \n        {\n            y=i;\n            m=z[i];\n        }\n        else\n        {\n            if (!o1) o1=i;\n            else o2=i;\n        }\n\n    if (((t[o1]-n[o1])*p[o1]+(t[o2]-n[o2])*p[o2])<=r)\n    {\n        r-=((t[o1]-n[o1])*p[o1]+(t[o2]-n[o2])*p[o2]);\n        ans++;\n        m--;\n        n[y]-=t[y];\n        n[o1]=0;\n        n[o2]=0;\n\n        m=min(m,r\/(t[o1]*p[o1]+t[o2]*p[o2]));\n        ans+=m;\n        r-=m*(t[o1]*p[o1]+t[o2]*p[o2]);\n\n        n[y]-=m*t[y];\n    }\n}\n\nLL z0()\n{\n    F(i,0,2)\n        am+=p[i]*t[i];\n\n    if (((t[0]-n[0])*p[0]+(t[1]-n[1])*p[1]+(t[2]-n[2])*p[2])<=r)\n    {\n        r-=((t[0]-n[0])*p[0]+(t[1]-n[1])*p[1]+(t[2]-n[2])*p[2]);\n        ans++;\n    }\n    m=r\/am;\n    ans+=m;\n    r-=m*am;\n}\n\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI s;\n    CII(n,0,2)\n    CII(p,0,2)\n    CI r;\n    \n    F(i,0,s.size()-1)\n    {\n        if (s[i]=='B') t[0]++;\n        if (s[i]=='S') t[1]++;\n        if (s[i]=='C') t[2]++;\n    }\n    \n    F(i,1,4)\n    {\n        int on=0;\n        F(i,0,2)\n        {\n            if (t[i]) z[i]=n[i]\/t[i];\n            else z[i]=0x7fffffffffffffff;\n            if (z[i]) on++;\n        }\n        if (on==3) z3();\n        if (on==2) z2();\n        if (on==1) z1();\n        if (on==0) z0();\n    }\n    CO ans L;\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0308. Keshi Is Throwing a Party<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u5229\u7528\u4e8c\u5206\uff0c\u5224\u65ad\u662f\u5426\u80fd\u627e\u5230\u4e2d\u95f4\u503cm\u4e2a\u4eba\u6ee1\u8db3\u9898\u76ee\u8981\u6c42\u3002<\/p>\n\n\n\n
int t;\nint n,a[200005],b[200005];\nint check(int m)\n{\n    int c=0;\n    F(i,1,n)\n        if (m-c-1<=a[i]&&c<=b[i]) c++;\n    return c>=m;\n}\n\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI t;\n    while (t--)\n    {\n        CI n;\n        F(i,1,n)\n            CI a[i]>>b[i];\n        \n        int l=0,r=n+1;\n        while (l<=r)\n        {\n            int m=(l+r)\/2;\n            if (check(m)) l=m+1;\n            else r=m-1;\n        }\n        CO r L;\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0309. Monthly Expense<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u5229\u7528\u4e8c\u5206\uff0c\u67e5\u627e\u5408\u9002\u7684\u82b1\u8d39\u503c\uff0cl\u7684\u521d\u59cb\u503c\u4e3a\u6bcf\u5929\u82b1\u8d39\u7684\u6700\u5c0f\u503c\uff0cr\u7684\u521d\u59cb\u503c\u4e3a\u603b\u82b1\u8d39\u3002\u5224\u65ad\u662f\u5426\u80fd\u5206\u51faM\u7ec4\u3002<\/p>\n\n\n\n
int n,m,a[100005];\nint check(int mid)\n{\n    int x=1,t=0;\n    F(i,1,n)\n    {\n        if (t+a[i]<=mid) t+=a[i];\n        else\n        {\n            t=a[i];\n            x++;\n        }\n    }\n    return x<=m;\n}\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI n>>m;\n    int l=0,r=0;\n    F(i,1,n)\n    {\n        CI a[i];\n        l=max(l,a[i]);\n        r+=a[i];\n    }\n    while (l<=r)\n    {\n        int mid=(l+r)\/2;\n        \n        if (check(mid)) r=mid-1;\n        else l=mid+1;\n    }    \n    CO l L;\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0310. New Year's Problem<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u5229\u7528\u4e8c\u5206\uff0cl\u548cr\u5bfb\u627ejoy\u503c\uff0c\u7136\u540e\u5c06\u77e9\u9635\u4e2d\u7684\u6bcf\u4e00\u4e2ajoy\u503c\u51cf\u53bb\u4e2d\u95f4\u503cm\uff0c\u5e76\u5224\u65ad\u6bcf\u4e00\u5217\u662f\u5426\u90fd\u6709\u4e00\u4e2a\u503c\u5927\u4e8em\uff0c\u4efb\u610f\u6709\u4e00\u884c\u6709\u4e24\u4e2a\u503c\u5927\u4e8em\u3002<\/p>\n\n\n\n
int t,n,m;\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI t;\n    while (t--)\n    {\n        CI m>>n;\n        int a[m+1][n+1];\n\n        int l=0x3f3f3f,r=0;\n        F(i,1,m)\n            F(j,1,n)   \n            {     \n                CI a[i][j];\n                l=min(l,a[i][j]);\n                r=max(r,a[i][j]);\n            }\n        \n        while (l<=r)\n        {\n            int mid=(l+r)\/2;\n\n            int b[m+1][n+1],fm[m+1]={0},fn[n+1]={0},f2=1,f3=0;\n            F(i,1,m)\n            {\n                F(j,1,n)\n                    if (a[i][j]>=mid)\n                    {\n                        fm[i]++;\n                        fn[j]++;\n                    }\n\n                if (fm[i]>=2) f3=1;\n            }\n\n            F(j,1,n)\n                if (!fn[j]) f2=0;\n\n            if (f2&&f3) l=mid+1;\n            else r=mid-1;\n        }\n        CO r L;\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#JC0311. Poisoned Dagger<\/h2>\n\n\n\n
\u9898\u76ee\u63cf\u8ff0<\/a><\/p>\n\n\n\n
\u5229\u7528\u4e8c\u5206\uff0c\u67e5\u627ek\u503c\uff0c\u5e76\u5224\u65adk\u503c\u4f24\u5bb3\u662f\u5426\u80fd\u8fbe\u5230h\u3002<\/p>\n\n\n\n
LL t,n,h,a[101];\n\nint check(LL m)\n{\n    LL s=m;\n    F(i,2,n)\n        s+=min(m,a[i]-a[i-1]);\n    return s>=h;\n}\n\nint main()\n{\n    \/\/ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);\n    CI t;\n    while (t--)\n    {\n        CI n>>h;\n        CII(a,1,n);\n        LL l=1,r=h;\n        while (l<=r)\n        {\n            LL m=(l+r)\/2;\n            if (check(m)) r=m-1;\n            else l=m+1;\n        }\n\n        CO l L;\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
#JC0301. Angry Cows \u9898\u76ee\u63cf\u8ff0 \u5229\u7528\u4e8c\u5206\uff0c\u6765\u67e5\u627e\u8ddd\u79bb\u503c\uff0c\u901a\u8fc7\u5224\u65ad\u8be5\u8ddd\u79bb\u503c\u662f\u5426\u80fd\u5b89\u6392\u7684\u4e0b\u6240\u6709\u7684\u725b\u6765\u8c03\u6574l\u548cr\u3002 # …<\/p>","protected":false},"author":1,"featured_media":1288,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,35],"tags":[12,34,22,39],"class_list":["post-1285","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-3","category-35","tag-12","tag-34","tag-22","tag-39"],"_links":{"self":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1285","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/comments?post=1285"}],"version-history":[{"count":1,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1285\/revisions"}],"predecessor-version":[{"id":1741,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1285\/revisions\/1741"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/media\/1288"}],"wp:attachment":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/media?parent=1285"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/categories?post=1285"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/tags?post=1285"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}