题解 | # D. Price Tags #

$[思维]$

有 $n$ 件商品，每件商品的价格为 $c_{i}$ ，每件商品上都贴着原来它自己价格 $c_{i}$ 的标签

现在你需要选择一个数 $x$ （ $x\geq 2$ ），然后将每件商品的价格 $c_{i}$ 变为 $\lceil \frac{c_{i}}{x} \rceil$

这时候原来的商品标签不再适用，你需要给每件商品贴上新的价格标签

但是旧标签可以复用，但只能贴在新价格和标签数字完全一样的商品上，每个标签只能用一次；不够的标签要花钱打印，每个标签打印成本是 $y$ 金币

求最大的收益（收益等于每件商品的新价格减去贴新标签的代价）

比如现在选择的数为 $x$ ，那么每件商品的新价格之和为 $\sum_{i=1}^{n}{ \lceil\frac{c_{i}}{x} \rceil }$ ，然后减去新价格标签的代价：所以得把原来 $c_{i}$ 出现的次数存下来，记为 $sum[c_{i}]$ ，也要把现在 $\lceil \frac{c_{i}}{x} \rceil$ 的出现的次数记下来，记为 $cnt[\lceil\frac{c_{i}}{x} \rceil]$ ，那么现在需要枚举所有可能出现的标签价格，最大标签价格为 $\lceil \frac{max(c_{1},c_{2},...,c_{n})}{x} \rceil$ ，记为 $max\_price$

所以此时的总收益为 $\sum_{i=1}^{n}{ \lceil\frac{c_{i}}{x} \rceil } - \sum_{i=1}^{max\_price}{max(0, cnt[i] - sum[i]) \times y}$ ，枚举 $x$ 再枚举每一个价格，时间复杂度近似为 $O(n^{2})$ ，超时了

首先 $x$ 需要只需要从 $1$ 枚举到 $max(c_{1}, c_{2}, ...,c_{n})$ ，因为如果 $x \geq max(c_{1},c_{2},...,c_{n})$ ，所有的 $\lceil \frac{c_{i}}{x} \rceil$ 都一直是 $1$

枚举到 $max(c_{1}, c_{2}, ...,c_{n})+1$ ，因为如果 $max(c_{1}, c_{2}, ...,c_{n}) = 1$ 时，直接跳过循环，不会枚举 $x$ ，因为 $x\geq 2$

然后只能优化的是枚举的每一个商品：现在不枚举每一件商品，而是枚举在当前 $x$ 的时候 $\lceil \frac{c_{i}}{x} \rceil$ 的值， $\lceil \frac{c_{i}}{x} \rceil$ 记为 $j$ ，那么有 $\lceil \frac{c_{i}}{x} \rceil = j$ ， $c_{i}$ 的范围为 $[(j-1)\times x + 1,j \times x]$ ，快速求 $[(j-1)\times x + 1,j \times x]$ 范围里面 $c_{i}$ 出现的次数，可以用前缀和。

$[(j-1)\times x + 1,j \times x]$ 范围里面 $c_{i}$ 出现的次数是 $\lceil \frac{c_{i}}{x} \rceil = j$ 的次数，即现在 $\lceil \frac{c_{i}}{x} \rceil$ 出现的次数，转化为了 $c_{i}$ 某个区间出现的次数！

那么现在时间复杂度为调和级数，约为 $O(nlogn)$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 200000 + 100;
int cnt[N], pre[N];

void solve(){
    
    memset(cnt, 0, sizeof(cnt));
    int n, y; cin >> n >> y;
    int Max = 0;
    for(int i = 1; i <= n; i ++){
        int x; cin >> x;
        cnt[x] ++;
        Max = max(Max, x);
    }    
    for(int i = 1; i < N; i ++) pre[i] = pre[i - 1] + cnt[i];
    int ans = -1000000000000000000;
    for(int x = 2; x <= Max + 1; x ++){
        int now_ans = 0;
        for(int j = 1; ; j ++){
            int l = (j - 1) * x + 1;
            int r = j * x;
            if(l > Max) break;
            r = min(r, Max);
            int now_cnt = pre[r] - pre[l - 1];
            now_ans += now_cnt * j;
            int add = max(0LL, now_cnt - cnt[j]);
            now_ans -= add * y;
        }
        ans = max(ans, now_ans);
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}