Educational Codeforces Round 24 F. Level Generation(三分)

题目链接：Educational Codeforces Round 24 F. Level Generation

题意：

给你n个点，让你构造ans条边，使得这ans条边中至少有一半是桥。

让你求ans的最大值。

题解：

首先我们将每一个点按顺序连起来，那么可以构成n-1个桥。

然后我们可以把其中的x个点拿出来连边，这些边都不是桥。

x个点最多能连x*(x-1)条边，然后剩下的n-x个点连的边将会构成桥。

然后就可以构造一个函数关系，详见check函数，然后三分一下就行了。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long ll;

int q;
ll n,ans;

ll check(ll mid)
{
    ll tmp=(mid*mid-mid)/2;
    if(n-mid>=tmp)return tmp+n-mid;
    else if(n-mid>=mid-1)return (n-mid)*2;
    else return mid-1;
}

int main(){
    scanf("%d",&q);
    while(q--)
    {
        scanf("%I64d",&n);
        ll l,r,mid,mmid;
        for(l=1,r=n;l<r-1;)
        {
            mid=l+r>>1,mmid=mid+r>>1;
            if(check(mid)>check(mmid))r=mmid;
            else l=mid;
        }
        printf("%I64d
",max(check(l),max(check(r),check(1))));
    }
    return 0;
}