隨機(jī) Random

2019-11-11 05:03:43

字體：大中小

供稿：網(wǎng)友

暴力

寫(xiě)起來(lái)簡(jiǎn)單，考場(chǎng)沒(méi)時(shí)間寫(xiě)正解也能騙30分時(shí)間復(fù)雜度：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); } }

尺取法

把第三重循環(huán)去掉，重點(diǎn)在break;那句，若最小差值已經(jīng)小于區(qū)間長(zhǎng)度，則沒(méi)有必要繼續(xù)第二層循環(huán)，因?yàn)榇藭r(shí)權(quán)值取決于區(qū)間長(zhǎng)度，而繼續(xù)第二層循環(huán)的話(huà)區(qū)間長(zhǎng)度只會(huì)越來(lái)越大時(shí)間復(fù)雜度：O(N2) $O(N^2)$ 然而……仍然不是正解，不過(guò)90分到手也不錯(cuò)了╭(╯^╰)╮

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; //兩個(gè)平衡樹(shù)； void Ins(int x) // 插入操作； { multiset<int>::iterator it,pre,nex;//定義迭代器變量； pre=nex=it=val.insert(x); // 在平衡樹(shù)val中插入當(dāng)前值，迭代器變量賦當(dāng)前插入值得位置為初值； if(it!=val.begin()) //如果不在平衡樹(shù)頂部則平衡樹(shù)dat中插入新生成的和前一個(gè)值的差值； { pre--; dta.insert(*it-*pre); } nex++; if(nex!=val.end()) //如果不在平衡樹(shù)底部則在平衡樹(shù)dat中插入新生成的和后一個(gè)值的差值； { 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中刪除和前一個(gè)值的差值； { pre--; dta.erase(dta.find(*it-*pre)); } nex++; if(nex!=val.end())//如果不在底部，則在dta中刪除和后一個(gè)值的差值； { dta.erase(dta.find(*nex-*it)); if(it!=val.begin()) dta.insert(*nex-*pre); } val.erase(it); //在val中也刪除當(dāng)前元素； }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';}