碰到一个挺奇怪的状况
查看原帖
碰到一个挺奇怪的状况
660641
0zhouyq楼主2023/4/18 21:40

我的代码在不开 O2 的情况下,AC×1+\times1+WA×3+\times3+TLE×6\times6,用时甚至到了1.20s,提交记录, 但一开 O2 直接 AC ,跑得飞快,最慢的点 16ms 就解决的,甚至 WA 的都变 AC 了,提交记录。

为啥?

下面是本人丑陋的代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[100001];
ll check(ll l,ll r){
	ll b[a[r]-a[l]+2];//是这句有问题吗?这么写只是为了省空间。
	for(ll i=0;i<=a[r]-a[l]+2;i++) b[i]=0;
	ll all=r-l+1;
	for(ll i=l;i<=r;i++){
		b[a[i]-a[l]]++;
	}
	ll lef=0,ret=0x3f3f3f3f3f3f3f3f;
	while(all){
		while(b[lef]<=0){
			lef++;
		}
		ll j=lef;
		b[lef]--;
		all--;
		while(b[j]+1<=b[j+1]&&b[j+1]){
			j++;
			b[j]--;
			all--;
		}
		ret=min(ret,j-lef+1);
	}
	return ret;
}
int main(){
	scanf("%lld",&n);
	if(n==0) printf("0");
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	ll lst=1,ans=0x3f3f3f3f3f3f3f3f,now=1;;
	for(ll i=2;i<=n;i++){
		if(a[i]>a[now]+1){
			ans=min(ans,check(lst,i-1));
			lst=i;
		}
		now=i;
	}
	ans=min(ans,check(lst,n));
	printf("%lld",ans);
	return 0;
}
2023/4/18 21:40
加载中...