随机 Random

2019-11-11 05:51:43

字体：大中小

来源：转载

供稿：网友

暴力

写起来简单，考场没时间写正解也能骗30分时间复杂度：O(N3) $O(N^3)$

#include<iostream>#include<cstdio>using namespace std;#define min(a,b) (a<b?a:b)#define max(a,b) (a>b?a:b)const int MAXN=1e6,INF=1e9+1;int na[MAXN+1];int n;int abs(int x){return x<0?-x:x;}int main(){ freopen("random.in","r",stdin); freopen("random.out","w",stdout); int i,j,k,un; int minv=INF,ans=INF; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&na[i]); for(i=1;i<n;i++) { for(j=i+1;j<=n;j++) { minv=INF; for(k=i;k<=j-1;k++) if(minv>abs(na[j]-na[k])) minv=abs(na[j]-na[k]); un=j-i+1; if(ans>max(minv,un)) ans=max(minv,un); } } PRintf("%d/n",ans); return 0;}

尺取法

把第三重循环去掉，重点在break;那句，若最小差值已经小于区间长度，则没有必要继续第二层循环，因为此时权值取决于区间长度，而继续第二层循环的话区间长度只会越来越大时间复杂度：O(N2) $O(N^2)$ 然而……仍然不是正解，不过90分到手也不错了╭(╯^╰)╮

for(int i=1;i<n;i++){ minv=INF; for(int j=i+1;j<=n;j++){ tmp=abs(a[i]-a[j]); if(minv>tmp){ minv=tmp; un=j-i+1; if(un<tmp) ans=min(ans,minv); else{ ans=min(ans,un); break; } } }}

正解#include<cstdio>#include<iostream>#include<set>using namespace std;inline void readi(int &x);const int maxn=1000005;int n,ans,a[maxn];multiset<int> val,dta; //两个平衡树； void Ins(int x) // 插入操作； { multiset<int>::iterator it,pre,nex;//定义迭代器变量； pre=nex=it=val.insert(x); // 在平衡树val中插入当前值，迭代器变量赋当前插入值得位置为初值； if(it!=val.begin()) //如果不在平衡树顶部则平衡树dat中插入新生成的和前一个值的差值； { pre--; dta.insert(*it-*pre); } nex++; if(nex!=val.end()) //如果不在平衡树底部则在平衡树dat中插入新生成的和后一个值的差值； { dta.insert(*nex-*it); if(it!=val.begin()) dta.erase(dta.find(*nex-*pre)); }}void Del(int x) //删除操作； { multiset<int>::iterator it,pre,nex; pre=nex=it=val.find(x); //找到x在val中迭代器变量的值，并将其赋为初值； if(it!=val.begin()) //如果不在顶部，则在dta中删除和前一个值的差值； { pre--; dta.erase(dta.find(*it-*pre)); } nex++; if(nex!=val.end())//如果不在底部，则在dta中删除和后一个值的差值； { dta.erase(dta.find(*nex-*it)); if(it!=val.begin()) dta.insert(*nex-*pre); } val.erase(it); //在val中也删除当前元素； }int main(){ freopen("random.in","r",stdin); freopen("random.out","w",stdout); readi(n);ans=n+1; for(int i=1;i<=n;i++) readi(a[i]); int l=1,r=0,v; while(l<n&&r<=n) { if(r==n) Del(a[l++]); else if(r<=l) Ins(a[++r]); else { v=*dta.begin(); if(r-l+1>v)Del(a[l++]); else Ins(a[++r]); } if(l<r) ans=min(ans,max(r-l+1,*dta.begin())); } printf("%d/n",ans); return 0;}inline void readi(int &x){char c;while(c=getchar(),c<'0'||c>'9');x=c-'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';}

上一篇：winfrom-窗体打开大小和全屏设置

下一篇：建造者模式