Codeforces Round #376 (Div. 2)F. Video Cards（前缀和）

题目链接：http://codeforces.com/contest/731/problem/F

题意：有n个数，从里面选出来一个作为第一个，然后剩下的数要满足是这个数的倍数，如果不是，只能减小为他的倍数，否则就舍弃掉，然后把没有舍弃的数的值加起来，求和的最大值;

4
3 2 15 9

就拿这个来说，当拿3当做第一个数时结果是3+15+9=27因为2不是3的倍数；当拿2作为第一个数时，结果是2+2+14+8=26因为3，15，9都不是2的倍数，所以只能减小;同理...求最大的和;

我们可以记录每个数出现的次数，然后记录前缀和，然后枚举每个数作为第一个数，当x作为第一个数时，我们可以枚举x的整数倍，然后每次找到整数j倍和j+1倍中的数出现了几次，这些数都是数x的j倍，然后求出对当前结果的贡献即可
时间复杂度为O(nlogn);

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<stdio.h>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
#define mod 1000000007
typedef long long LL;
//////////////////////////////////////////////////////////////
const int INF = 0x3f3f3f3f;
const int N = 200521;
const double eps = 1e-8;

int n, a[N];
LL pre[N*2];

int main()
{
    while(scanf("%d", &n)!=EOF)
    {
        met(pre, 0);
        for(int i=0; i<n; i++)
        {
            scanf("%d", &a[i]);
            pre[a[i]]++;
        }
        
        sort(a, a+n);
        int m = unique(a, a+n) - a;
        
        for(int i=1; i<=a[m-1]*2; i++)
            pre[i] += pre[i-1];
            
        LL ans = 0;
        for(int i=0; i<m; i++)
        {
            LL ret = 0;
            for(int j=1; a[i]*(j+1) <= a[m-1]*2; j++)
            {
                LL cnt = pre[(j+1)*a[i]-1] - pre[j*a[i]-1];
                ret += a[i]*j * cnt;
            }
            ans = max(ans, ret);
        }
        printf("%lld
", ans);
    }
    return 0;
}