这么玄学的时间复杂度都能过?(356ms)(o2 233ms)
查看原帖
这么玄学的时间复杂度都能过?(356ms)(o2 233ms)
846349
log_and_long楼主2023/5/26 11:15

是不是数据太水了?

#include<bits/stdc++.h>
using namespace std;
int a,b,e,ans=0x7fffffff;
int c[10000001];
int jy;
inline int read() {
	int s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
inline void write(int n)
{
	if(n<0)
	{
		putchar('-');
		n=-n;
	}
	if(n>9)write(n/10);
	putchar(n%10+'0');
}
int work(int x){
	x--;
	int y=b,minn=0x7fffffff;
	if(x-y<jy){
		if(c[x]<=c[jy]){
			jy=x;
		}
		return c[jy];
	}
	if(c[x]<=c[jy]){
		jy=x;
		return c[x];
	}
	while(y--){
		if(minn>=c[x]){
			minn=c[x];
			jy=x;
		}
		x--;
	}
	return c[jy];
}
int main(){
	a=read();
	b=read();
	for(int i=1;i<=a;i++){
		e=b;
		c[i]=read();
	}
	write(0);
	printf("\n");
	for(int i=1;i<=b;i++){
		if(ans>=c[i]){
			ans=c[i];
			jy=i;
		}
		write(ans);
		printf("\n");
	}
	for(int i=b+2;i<=a;i++){
		write(work(i));
		printf("\n");
	}
	return 0;
}
2023/5/26 11:15
加载中...