D - Worst Case

原题地址
思路:

使 a <= b
找到最大的C使得 <mark>C * C<A * B</mark>.
如果 c * (c + 1) >= a * b ,那么可以构造 c + c - 1 个 数对 ,减去 一个包含 a 的 ,则答案为 2 * c - 2

如果 c * (c + 1) < a * b ,那么可以构造 c + c 个 数对 ,减去 一个包含 a 的 ,则答案为 2 * c - 1

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
//#inlcude<stringstream>
#define ll long long
#define MODD 1000000007
using namespace std;
ll arr[1000000]={0};
ll brr[1000000]={0};
int main() {
    //1 12 4 11 14 57 31 671644785
    ll n;cin>>n;
    for(int i=0;i<n;i++){
        ll a, b,sum=0;cin >>a>>b;
        ll mul = a*b;ll c = sqrt(mul);
        ll mi = a,ma=b;
        mi = min(mi,b);
        if(c*c==mul)c--;
        if(c*(c+1)>=mul)sum--;
        if(c>=mi)sum--;
        sum+=2*c;
        cout<<sum<<endl;
    }
    return 0;
}

全部评论

相关推荐

半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
06-15 18:44
黄淮学院 Java
Lynn012:如果是居民楼还是算了吧,看着有点野呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务