本文主要是介绍sincerit tokitsukaze and RPG，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://ac.nowcoder.com/acm/contest/308/B
来源：牛客网
题目描述
tokitsukaze最近沉迷一款RPG。
这个RPG一天有k分钟，每一天从第1分钟开始。
有n种怪物，第i种怪物每天第一次出现的时间为Xi分钟，第二次出现的时间为2Xi分钟，第三次出现的时间为3Xi分钟…同一时刻出现的怪物种类越多，打怪获得的经验也越高。
为了高效练级，tokitsukaze想知道在一天内出现怪物种类最多的时间点会出现多少种怪物，这样的时间点有多少个。
输入描述:
第一行包括2个正整数n，k(1≤n≤105，1≤k≤106)，表示有n种怪物，一天有k分钟。
接下来一行包括n个正整数X(1≤Xi≤10^6)，含义如题面所示。
输出描述:
输出一行，包括两个整数a，b。
a表示怪物种类数，b表示时间点的个数。
示例1
输入
复制
3 6
2 2 3
输出
复制
3 1
说明
在第6分钟时，3种怪物都出现了。
示例2
输入
复制
3 5
2 2 3
输出
复制
2 2
说明
在第2分钟和第4分钟时，第一种和第二种怪物出现了。
示例3
输入
复制
6 10
1 2 3 4 5 6
输出
复制
4 1
说明
在第6分钟时，出现了第一种、第二种、第三种、第六种怪物。
示例4
输入
复制
3 5
6 6 6
输出
复制
0 5
说明
在第1分钟、第2分钟、第3分钟、第4分钟、第5分钟，都没有出现怪物。
这个代码超时,不知道哪里会耗时
#include <stdio.h>
#include <cstring>
const int N = 1e6+5;
int dp[N];
int main() {int n, k, x;while (~scanf("%d%d", &n, &k)) {memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++) {scanf("%d", &x);for (int j = x; j <= k; j+= x) dp[j]++;}int time = 0, sum = 0; // time表示出现的次数，sum表示种类 for (int i = k; i >= 1; i--) {if (dp[i] > sum) {sum = dp[i];time = 1;} else if (dp[i] && dp[i] == sum) {time++;}}printf("%d %d\n", sum, sum==0?k:time);}return 0;
}
改进：
#include <stdio.h>
#include <cstring>
const int N = 1e6+5;
int cnt[N];
int temp[N];
int main() {int n, k, x;while (~scanf("%d %d", &n, &k)) {memset(cnt, 0, sizeof(cnt));for (int i = 1; i <= n; i++) {scanf("%d", &x);temp[x]++;}for (int i = 1; i <= k; i++) {if (temp[i]) {for (int j = i; j <= k; j+=i) cnt[j] += temp[i]; //要用另一个数组存数据不然会覆盖 }}//for (int i = 1; i <= k; i++) printf("%d ", cnt[i]); int mx = 0, sum = 0; // mx表示出现的种类，sum表示次数for (int i = 1; i <= k; i++) if (cnt[i] > mx) mx = cnt[i];for (int i = 1; i <= k; i++) if (cnt[i] == mx) sum++;printf("%d %d\n", mx, sum);}return 0;
}这篇关于sincerit tokitsukaze and RPG的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
