2015ACM-ICPC亚洲区域赛EC-Final A：Boxes and Balls

February 26, 2016

题目 PDF 下载

题意：f(m) = m*(m+1)/2. 找到最大的 f(m)，使 f(m) <= N. 输出这个 f(m)。

直接解方程就可以，需要注意的是开根号过程中会出现精度问题，我们在解出来的 m 的附近找一小范围就可以。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    for(int cas = 1; cas <= t; cas++){
        long long n;
        scanf("%lld", &n);
        long long m = (long long)((sqrt(1+8.0*n)-1)/2);
        m += 2;
        while(1){
            long long k = m*(m+1)/2;
            if(k<=n){
                printf("Case #%d: %lldn", cas, k);
                break;
            }

            m--;
        }

    }
    return 0;
}

还有一种方法，二分，找到最大的 m 满足 f(m) > n. 注意下精度问题即可。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
long long n;
long long f(long long x){
    return x*(x+1)/2;
}

bool judge(long long x){
    if(f(x) > n)
        return 1;
    return 0;
}
int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    for(int cas = 1; cas <= t; cas++){
        scanf("%lld", &n);
        long long l = 1, r = 1e10;

        while(l <= r){
            long long mid = l+(r-l)/2;
            if(judge(mid))
                r = mid-1;
            else l = mid+1;
        }
        //cout << l << endl;
        //cout << r << endl;
        l = f(--l);
        printf("Case #%d: %lldn", cas, l);
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]