首页 > 代码库 > HDU_2446

HDU_2446

http://acm.hdu.edu.cn/showproblem.php?pid=2446

 

打表,二分查找,注意查找最后的判断。

 

#include<cstdio>#define N 2000017using namespace std;__int64 x[N] = {0},y[N] = {0};__int64 fun1(__int64 a){    __int64 l = 1,r = N,mid;    while(l < r)    {        mid = (l+r)/2;        if(y[mid] < a)        {            l = mid+1;        }        else if(y[mid] > a)        {            r = mid-1;        }        else        {            return mid;        }    }    if(y[l] < a)    {        return l+1;    }    return l;}__int64 fun2(__int64 a){    __int64 l = 1,r = N;    while(l < r)    {        __int64 mid = (l+r)/2;        if(x[mid] < a)        {            l = mid+1;        }        else if(x[mid] > a)        {            r = mid-1;        }        else        {            return mid;        }    }    if(x[l] < a)    {        return l+1;    }    return l;}int main(){    for(int i = 1;i <= N;i++)    {        x[i] = x[i-1]+i;        y[i] = y[i-1]+x[i];    }    int n;    scanf("%d",&n);    while(n--)    {        __int64 a,b,c;        __int64 temp1;        scanf("%I64d",&temp1);        a = fun1(temp1);        __int64 temp2 = temp1-y[a-1];        b = fun2(temp2);        c = temp2-x[b-1];        printf("%I64d %I64d %I64d\n",a,b,c);    }    return 0;}

 

HDU_2446