题意：问你n个点的情况构造一个图使得这个图的边最多(这个图需要满足桥的数量大于等于边总数的一半）
解：
1、考虑图中构造一部分内部尽量多的边，对这一份的外部的点，这个分量只和外部每个点只有一条边。
那么 考虑这部分的大小是k,
若想满足桥的数量至少一半那么
该部分分量的边也就是非桥边不可以超过桥边
所以边的数量为f(k)==min(n-k,k*(k-1)/2)+n-k;
画图知f(k)为上凸函数满足三分性质
#include<bits/stdc++.h> #define en '\n' #define ll long long using namespace std; const ll inf=0x3f3f3f3f; const ll maxn = 1e5+3; const ll maxm=maxn<<2; ll n; ll rd(){ ll tem;scanf("%I64d",&tem);return tem; } ll f(ll x){ ll tem1; if(x&1){tem1=x*((x-1)>>1);} else tem1=(x>>1)*(x-1); ll tem2=n-x; return min(tem1,tem2)+(n-x); } signed main() { #ifdef local freopen("input2.txt","r",stdin); #endif ll q=rd(); while(q--){ n=rd(); ll l=0,r=n; if(n==1){ cout<<0<<en; continue; } while(l+1<r){ ll lmid=(l+r)>>1; ll rmid=(lmid+r)>>1; if(f(lmid)>f(rmid)){ r=rmid; }else{ l=lmid; } } cout<<f(l)<<en; } return 0; }
