二分离散化求助
查看原帖
二分离散化求助
705702
user100566楼主2024/12/12 19:45

正确通过样例。

非文末回车导致的格式错误问题,由代码中的 if(t) putchar('\n'); 保证。

非多测清空问题,代码定义中的唯一非覆盖变量 bucket 由于双指针循环的终点为 i=n, j=n,最终 bucket 是正确清空的。

#include <cstdio>
#include <algorithm>
using namespace std;

int T, n, a[1000000], b[1000000];
bool bucket[1000000];

int main(){
	scanf("%d", &T);
	for(int t=0; t<T; ++t){
		if(t) putchar('\n');
		scanf("%d", &n);
		for(int i=0; i<n; ++i){
			scanf("%d", a+i);
			b[i] = a[i];
		}
		sort(b, b+n);
		int* b_ed = unique(b, b+n);
		int ans = 0;
		for(int i=0, j=0; i<n; ++i){
			while(j<n){
				int a_ = lower_bound(b, b_ed, a[j])-b;
				if(!bucket[a_]){
					bucket[a_] = true;
					++j;
				}else break;
			}
			ans = max(ans, j-i);
			bucket[lower_bound(b, b_ed, a[i])-b] = false;
		}
		printf("%d", ans);
	}
	return 0;
}

2024/12/12 19:45
加载中...