首页 > 代码库 > cf 760B.Frodo and pillows

cf 760B.Frodo and pillows

二分,判断条件就是最小情况(设当前k位取x)比剩余值(m-x)要小。(貌似又做麻烦了2333)

 1 #include<bits/stdc++.h>
 2 #define LL long long 
 3 #define  N 100005
 4 using namespace std;
 5 inline int ra()
 6 {
 7     int x=0,f=1; char ch=getchar();
 8     while (ch<0 || ch>9) {if (ch==-) f=-1; ch=getchar();}
 9     while (ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}
10     return x*f;
11 }
12 int n,m,k;
13 bool check(LL x)
14 {
15     if (x==1) return m>=n;
16     LL mx1=(k-1)*(x+1+x+k-1)>>1,mn1;
17     LL mx2=(n-k)*(x+1+x+n-k)>>1,mn2;
18     if (x>=k) mn1=(k-1)*(x+x-k)>>1;
19     else mn1=((x-1)*(x)>>1)+(k-x);
20     if (x>=n-k) mn2=(n-k)*(x-1+x-n+k)>>1;
21     else  mn2=((x-1)*(x)>>1)+(n-k-x+1);
22     if (mn1+mn2>m-x) return 0;
23     return 1;
24 }
25 int main()
26 {
27     n=ra(); m=ra(); k=ra();
28     int l=0,r=m;
29 //    check(3); while (1);
30     while (l<r)
31     {
32         int mid=l+r>>1;
33         if (check(mid)) l=mid+1;
34         else r=mid;
35     }
36     if (check(l)) cout<<l; else cout<<l-1;
37     return 0;
38 }

 

cf 760B.Frodo and pillows