A simple Blog for wyx I've been down the bottle hoping.
Codeforces 731F Video cards 筛法
发表于: | 分类: Oi | 评论:0 | 阅读:53

题目大意
给定$n$个数,选择一个作为打头的,然后把剩余比他大的全都变成打头的倍数(只能减法),比他小的舍弃,问选谁打头最得到的和最大,输出这个和
数字的个数和大小均小于200000

考试的时候发现这题A的比$E$还多,然后就转过来写,这题对于中国Oier来说实在是送分……

首先,可以发现,对于一个基数$base$,在$[kbase,(k+1)base)$的数字,对于答案的贡献其实都是$k*base$,然后这就是道益智的思博题目了,对于一个数,扫一下他的所有倍数,然后就能统计出各个区间都有多少个数,对应权值计算一下就行了,筛法的时间复杂度是$O(n\log{n})$的,但是得判重,然后自己维护一个权值的前缀\后缀和加加减减玩玩就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int MAX = 200000+5;
const int N = MAX;
using namespace std;
typedef long long LL;

bool vis[N];
int sum[N],n,a[N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    int n = read();
    for(int i=1;i<=n;++i) a[i] = read(),sum[a[i]] ++;
    for(int i=MAX;i>=1;--i) sum[i]+= sum[i+1];
    
    sort(a+1,a+n+1);
    LL ans = 0;
    
    for(int i=1;i<=n;++i)
    {
        if(vis[a[i]])continue;
        int tt = MAX / a[i];
        int times = 0;      
        LL tmpans = 0;
        
        for(int j=tt;j>=1;--j)
        {
            int tmp = j * a[i];
            vis[tmp] = 1;
            tmpans += (LL)(sum[tmp] - times)*(LL)tmp;
            times = sum[tmp];
        }
        ans = max(ans,tmpans);
    }
    
    cout << ans << endl;
        
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP