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 = ;
const double eps = 1e-; int n, a[N];
LL pre[N*]; int main()
{
while(scanf("%d", &n)!=EOF)
{
met(pre, );
for(int i=; i<n; i++)
{
scanf("%d", &a[i]);
pre[a[i]]++;
} sort(a, a+n);
int m = unique(a, a+n) - a; for(int i=; i<=a[m-]*; i++)
pre[i] += pre[i-]; LL ans = ;
for(int i=; i<m; i++)
{
LL ret = ;
for(int j=; a[i]*(j+) <= a[m-]*; j++)
{
LL cnt = pre[(j+)*a[i]-] - pre[j*a[i]-];
ret += a[i]*j * cnt;
}
ans = max(ans, ret);
}
printf("%lld\n", ans);
}
return ;
}
 
上一篇:NuGet学习笔记(2)——使用图形化界面打包自己的类库(转)


下一篇:WMI参数介绍