首页 > 代码库 > 2014 Super Training #7 B Continuous Login --二分

2014 Super Training #7 B Continuous Login --二分

2024-07-11 09:23:53   224人阅读

原题：ZOJ 3768 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3768

一个结论：一个正整数总能用不超过三个前n项相加表示。

先找一个的，在找两个，三个的，二分找，用lower_bound函数。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <vector>using namespace std;#define N 16007int sum[N];void init(){    sum[0] = 0;    for(int i=1;i<16000;i++)        sum[i] = sum[i-1] + i;}int main(){    int t,n,i,j;    init();    int a,b;    int x,y,z;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        int flag = 0;        int t = lower_bound(sum,sum+16000,n)-sum;        if(sum[t] == n)        {            printf("%d\n",t);            continue;        }        for(i=t;i&&2*sum[i]>=n;i--)        {            if(flag == 2)                break;            int lef = n-sum[i];            int t2 = lower_bound(sum,sum+16000,lef)-sum;            for(j=t2;j&&sum[i]+sum[j]*2>=n;j--)            {                if(flag == 2)                    break;                if(sum[i]+sum[j]==n)                {                    flag = 2;                    a = i,b = j;                    break;                }                else if(flag == 3)                    break;                else if(sum[i]+sum[j]<n)                {                    int lef2 = n-sum[i]-sum[j];                    int t3 = lower_bound(sum,sum+16000,lef2)-sum;                    if(sum[t3] == lef2)                    {                        flag = 3;                        x = i,y = j,z = t3;                        break;                    }                }            }        }        if(flag == 2)            printf("%d %d\n",a,b);        else if(flag == 3)            printf("%d %d %d\n",x,y,z);    }    return 0;}
View Code

 


联系
我们