網(wǎng)址：https://ac.nowcoder.com/acm/contest/4784/C

題目描述

在圖論的數(shù)學(xué)領(lǐng)域，完全圖是一個簡單的無向圖，其中每對不同的頂點之間都恰連有一條邊相連?！俣劝倏?br>現(xiàn)在給定一個包含 {n}n 個頂點的完全圖，你可以刪掉圖中的一些邊，但是刪掉的邊不能超過 {m}m 條，請問刪去邊之后的圖最多能有幾個連通分量？

輸入描述:

第一行包含一個數(shù)字 {T}T，表示測試數(shù)據(jù)組數(shù)
接下來 {T}T 行，每行兩個正整數(shù){n}n,{m}m，中間用空格隔開

輸出描述:

輸出 {T}T 行，每行一個整數(shù)表示答案

輸入

2
5 1
5 5

輸出

1
2

備注:

1≤T≤10000,1≤n,m≤10^18

題解：

這里要明白對于一個結(jié)點為n的完全圖，如果要分為兩份，一份x,一份y,那么所需要斷開的邊數(shù)為xy,因為這兩份不能相連，而原本其中一份(有x個結(jié)點)中的所有結(jié)點(共x個)，每個都與另一份中的所有結(jié)點(共y個結(jié)點)都相連，多以最少需要斷去xy條邊，而x+y=n（常數(shù)），所以其中一份為1時最好。
那么每次加一個連通分量，所需要最少短邊:n-1，n-2,....n-k;

AC代碼：

#include<iostream>
#include<cmath>
using namespace std;
const long long int maxn=1e18+10;
long long int n,m,ans,mid;
bool Check(long long int x){
    if(x*(2*n-x-1)/2>m) return true;
    else return false;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;        
        long long int l=0,r=min(maxn*2/n,n);
        ans=r;
        while(l<=r){
            mid=(l+r)/2;
            if(Check(mid)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
} 

打卡第12天，原明日更好。