CodeForces 287B Pipeline

思路：二分答案，时间复杂度O(nlgn).

若个数为x，那么算出这种情况下提供的水管的最大值和最小值与n比较即可，注意x个分离器需要减去x-1个水管。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long int
using namespace std;
LL n,k;
LL calSum(LL ba,LL i){
    return ((2*ba + i - 1) * i)/2;
}
LL bin_search(LL l,LL r){
    LL ans = 0x7fffffff;
    while(l <= r){
        LL mid = (l + r) >> 1;
        LL up = min(n + mid - 1,k);
        LL tmp1 = calSum(2,mid),tmp2 = calSum(up - mid + 1,mid);
        if(tmp1 <= n + mid - 1 && tmp2 >= n + mid -1){
            ans = min(ans,mid);
            r = mid - 1;
        }
        else if(tmp1 > n + mid - 1) r = mid - 1;
        else if(tmp2 < n + mid - 1) l = mid + 1;
    }
    if(ans != 0x7fffffff) return ans;
    else return -1;
}
int main(){
    while(cin >> n >> k){
        if(n == 1) printf("0n");
        else cout << bin_search(1,k-1) << endl;
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!