自动搬运

查看原文

来自洛谷，原作者为

	MingDynasty 最后在线时间:2025.8.23 21:03|team/76415出题组|开局一个碗,结局一根绳|坐标你猜|小升初蒟蒻,欢迎吊打|5天内2小号互关(大号paste/lb3d6tr9),可提醒,不可炸铃接龙|题解不懂私|主页article/hu9a8skr

搬运于2025-08-24 23:14:16，当前版本为作者最后更新于2025-04-22 14:53:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

一道值得回味的模拟题。

题目思路：

为方便起见，我们把压缩的时间记为 $s$ 数组。

我们使用 STL 中的 map 来把所有的时间压缩起来，再遍历每一个压缩后的时间，每次把 $\min(m,s_i)$ 加入答案，输出即可。

之所以这么做，是因为当前的 $s_i$ 如果不够上限访问次数，就都可以访问。如果当前的 $s_i$ 大与上限访问次数，那就加 $m$ 即可，毕竟剩下的都访问不了。

注意枚举压缩时间上限是未压缩时间最大值 $\div N$。

时间复杂度 $O(n \log n)$，可以通过本题。

Code：

/*
	Auther:MingDynasty
	Problem:https://www.luogu.com.cn/problem/P12279
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,l,maxn,ans,t;
map<int,int>s;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>l;
    for (int i=1;i<=l;i++){
        cin>>t;
        maxn=max(maxn,t);
        s[t/n]++;
    }
    for(int i=0;i<=maxn/n;i++) ans+=min(m,s[i]);
    cout<<ans;
    return 0;
}

祝大家通过本题！