tokitsukaze and RPG（暴力优化）

链接：https://ac.nowcoder.com/acm/contest/308/B

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

tokitsukaze最近沉迷一款RPG。

这个RPG一天有k分钟，每一天从第1分钟开始。

有n种怪物，第i种怪物每天第一次出现的时间为Xi分钟，第二次出现的时间为2*Xi分钟，第三次出现的时间为3*Xi分钟......同一时刻出现的怪物种类越多，打怪获得的经验也越高。

为了高效练级，tokitsukaze想知道在一天内出现怪物种类最多的时间点会出现多少种怪物，这样的时间点有多少个。

输入描述:

第一行包括2个正整数n，k(1≤n≤10^5，1≤k≤10^6)，表示有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分钟，都没有出现怪物。

题解：参加牛客网比赛的第二场，感觉难度。。有点大，虽然感觉题目很容易有想法，但是实在是难以ac，多与这道题，我一开始的想法是最小公倍数，然后就一直WA，多亏了大佬们的提醒，明白了这种解法的错误性，然后尝试暴力去解，单纯暴力肯定会超时的，所以优化问题就是个关键，优化的问题在代码中能够体现

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

int a[1000005];

int cnt[1000005];

int num[1000005];

int main() {

	int n,k;

	cin>>n>>k;

	for(int t=1; t<=n; t++) {

		scanf("%d",&a[t]);

	}

	sort(a+1,a+n+1);

	for(int t=1; t<=n; t++) {

		cnt[a[t]]++;

	}

	for(int t=1; t<=a[n]; t++) {

		if(cnt[t]) {

			for(int j=1;j*t<=k; j++) {

				num[j*t]+=cnt[t];

			}

		}

	}

	int maxn=0,sum=0;

	for(int t=1; t<=k; t++) {

		if(num[t]>maxn)maxn=num[t],sum=1;

		else if(num[t]==maxn)sum++;

	}

	printf("%d %d\n",maxn,sum);

	return 0;

}

巴特西

tokitsukaze and RPG（暴力优化）

题目描述

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

最新文章

热门文章