F. Video Cards

题目链接

Codeforces Round #376 (Div. 2)--F. Video Cards

题解

高档题。题意大概是给定一堆显卡,要求你指定一个主显卡,最终效益为所有显卡降低功率至主显卡倍数之后的功率之和。
首先将输入数据预处理为前缀和,允许快速求出功率在某一区间内的显卡数量,其次枚举每一功率的显卡作为主显卡快速求解即可。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int MOD = 1e9 + 7;
const int inf = (1 << 31) - 1;
const ll INF = 1ll << 60;

ll n, ans;
ll input[MAXN];
ll num[MAXN];
ll q1;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> input[i];
        num[input[i]]++;
    }
    for (int i = 1; i <MAXN; i++) {
        num[i] += num[i - 1];
    }
    for (int i = 1; i < MAXN; i++) {
        if (num[i] == num[i - 1])continue;
        q1 = 0;
        for (int j = i; j < MAXN; j += i) {
            q1 += (num[min(j + i - 1, MAXN - 1)] - num[j - 1])*j;
        }
        ans = max(ans, q1);
    }
    cout << ans << endl;
}

标签: implementation, brute force, data structures, number theory

添加新评论