题目链接

http://acm.tju.edu.cn/toj/showp4113.html

题目大意

给出 n 个数,求对于某个 x ,使得所有数除 x 得到的商和余数总和最小。

题解

我们可以通过以下两步转换获得一个新的式子。

A[i] % X = A[i] - (A[i]/X)*X;

A[i] % X + (A[i]/X) = A[i] - (A[i]/X)*(X - 1);

因为 (A[i]/X)*(X - 1) 的特性,我们可以枚举 X ,并且统计出所有在 X*(Y - 1) 到 X*Y - 1 范围内数的个数,这个区间每个数通过计算可以贡献 (X - 1)*(Y - 1) 的值,从中选出最优的 X 。

代码

//
//  main.cpp
//  bc
//
//  Created by 林海鸿 on 15/2/7.
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int N = 1000000, A = 1000000;
int sum[N + 5], a[N + 5];

int main() {
    int  T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d",&n);
        long long t_sum = 0;
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            t_sum += (long long)a[i];
            ++sum[a[i]];
        }
        for (int i = 1; i <= N; ++i) sum[i] += sum[i - 1];
        long long ans = t_sum;
        for (int i = 2; i <= A; ++i) {
            long long temp = 0;
            for (int j = 2; i*(j - 1) - 1 <= A; ++j) {
                long long l = min(i*(j - 1) - 1, A), r = min(i*j - 1, A);
                temp += (sum[r] - sum[l])*(long long)(j - 1);
            }
            ans = min(ans, t_sum - temp*(long long)(i - 1));
        }
        printf("%lld\n", ans);
    }
    return 0;
}

转载保留版权:http://haipz.com/blog/i/6508 - 海胖博客