频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
Codeforces Round #376 (Div. 2) F. Video Cards 数论+数据结构+前缀和
2016-10-25 09:48:12         来源:ProLights的博客  
收藏   我要投稿

F. Video Cards

 

time limit per test

 

1 second

 

memory limit per test

 

256 megabytes

 

input

 

standard input

 

output

 

standard output

 

 

Little Vlad is fond of popular computer game Bota-2. Recently, the developers announced the new add-on named Bota-3. Of course, Vlad immediately bought only to find out his computer is too old for the new game and needs to be updated.

There arenvideo cards in the shop, the power of thei-th video card is equal to integer valueai. As Vlad wants to be sure the new game will work he wants to buy not one, but several video cards and unite their powers using the cutting-edge technology. To use this technology one of the cards is chosen as the leading one and other video cards are attached to it as secondary. For this new technology to work it's required that the power of each of the secondary video cards is pisible by the power of the leading video card. In order to achieve that the power of any secondary video card can be reduced to any integer value less or equal than the current power. However, the power of the leading video card should remain unchanged, i.e. itcan'tbe reduced.

Vlad has an infinite amount of money so he can buy any set of video cards. Help him determine which video cards he should buy such that after picking the leading video card and may be reducing some powers of others to make them work together he will get the maximum total value of video power.

Input

 

The first line of the input contains a single integern(1?≤?n?≤?200?000)— the number of video cards in the shop.

The second line containsnintegersa1,a2, ...,an(1?≤?ai?≤?200?000)— powers of video cards.

 

Output

 

The only line of the output should contain one integer value— the maximum possible total power of video cards working together.

 

Examples

 

input

 

4
3 2 15 9

 

output

 

27

 

input

 

4
8 2 2 7

 

output

 

18

 

 

Note

 

In the first sample, it would be optimal to buy video cards with powers3,15and9. The video card with power3should be chosen as the leading one and all other video cards will be compatible with it. Thus, the total power would be3?+?15?+?9?=?27. If he buys all the video cards and pick the one with the power2as the leading, the powers of all other video cards should be reduced by1, thus the total power would be2?+?2?+?14?+?8?=?26, that is less than27. Please note, that it's not allowed to reduce the power of the leading video card, i.e. one can't get the total power3?+?1?+?15?+?9?=?28.

In the second sample, the optimal answer is to buy all video cards and pick the one with the power2as the leading. The video card with the power7needs it power to be reduced down to6. The total power would be8?+?2?+?2?+?6?=?18.

 

Source

Codeforces Round #376 (Div. 2)

 

My Solution

//这题虽然是F题,但属于Div.2 D题难道,所以归类于Div.2 D(或 Div.1 B)了

数论+数据结构+前缀和

就是以前用树状数组的感觉,比如有一个数x,就在以x为下标的地方插入一个 1,如果删除这个就在下标为x的地方插入一个-1, 这样要查询小于等于k的数的个数只要get(k)就好。

这里不需要维护,所以只要用一个前缀和数组,就可以直接预处理出来。

即对于每个a[i]就在 sum[a[i]]++;

读入完以后预处理出前缀和,for i = 1 ~ maxa, sum[i] += sum[i - 1];

然后扫一遍i = 1 ~ maxa,对于每个i在a[maxn]数组中出现过的i,(即 sum[i] - sum[i - 1] > 0)的地方,

for(j = 1; j <= maxa; j += i) //每次处理从 j 到 j + i - 1 的数,这些数都会作为 j 加到 s 里去

每次 求出 这个区间上的右端点 r = min(maxa, j + i - 1); //因为最后一次的右端点可能不是 j + i - 1;

然后 s += j * (sum[r] - sum[j - 1]); //从 j 到 j + i - 1 的数的个数

处理完后,刷新 ans = max(ans, s);

复杂度 O(sigma(maxa / i)) //这里大概是 sigma(maxa / i ==2.5e6

 

 

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;

LL a[maxn], sum[maxn];

int main()
{
    #ifdef LOCAL
    int t = 0;
    for(int i  = 1; i < (int)2e5; i++){
        t += ((int)2e5) / i;
    }
    cout << "O(sigma(maxa / i)) == " << t << "\n" << endl;
    freopen("f.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum[a[i]]++;
    }


    LL i, j, s, r, maxa = 2e5;
    for(i = 1; i <= maxa; i++) sum[i] += sum[i - 1];
    sort(a, a + n);
    for( i = 1; i <= maxa; i++){
        if(sum[i] - sum[i - 1]){
            s = 0;
            for(j = i; j <= maxa; j += i){
                if(j > a[n - 1]) break;
                r = min(maxa, j + i - 1);
                s += j * (sum[r] - sum[j - 1]);
            }
            ans = max(ans, s);
        }
    }

    cout << ans << endl;

    #ifdef LOCAL
    memset(sum, 0, sizeof sum);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:Codeforces Round #376 (Div. 2) C. Socks 并查集+贪心、图论
下一篇:Unity3D官方案例 - 2DGame - 帽子接球
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站