程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 484B Maximum Value

CodeForces 484B Maximum Value

編輯：C++入門知識

CodeForces 484B Maximum Value

題意：

a序列有n（2*10^5）個數字問在a[i]>=a[j]的情況下 a[i]%a[j]的最大值是多少

思路：

感覺是一道挺亂來的題……

我們可以將ans表示為a[i]-k*a[j] 這樣我們枚舉k只要知道比k*a[j]大但是不到(k+1)*a[j]的值就好了考慮到a[i]只要10^6大因此可以用一個last數組記錄小於等於i的數組中的數字因此只要拿出last[(k+1)*a[j]-1]就好

暴力可能會T有一些可以讓程序加速的方法輸入開掛 a數字去重從大到小枚舉a[i]當ans>=a[i]時候可以break

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define N 200010
#define M 1000010

int a[N], last[M];
int n, ans;

inline void scand(int &ret) {
	char c;
	ret = 0;
	while ((c = getchar()) < '0' || c > '9')
		;
	while (c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0'), c = getchar();
}

int main() {
	scand(n);
	for (int i = 1; i <= n; i++) {
		scand(a[i]);
		last[a[i]] = a[i];
	}
	for (int i = 1; i < M; i++) {
		if (!last[i])
			last[i] = last[i - 1];
	}
	sort(a + 1, a + n + 1);
	n = unique(a + 1, a + n + 1) - a - 1;
	for (int i = n - 1; i >= 1; i--) {
		if (a[i] <= ans)
			break;
		for (int j = a[i] * 2; j < M && j - a[i] <= a[n]; j += a[i]) {
			ans = max(ans, last[j - 1] % a[i]);
		}
		ans = max(ans, last[M - 1] % a[i]);
	}
	printf("%d\n", ans);
	return 0;
}