隨機 Random

2019-11-11 04:23:31

字體：大中小

來源：轉載

供稿：網友

暴力

寫起來簡單，考場沒時間寫正解也能騙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); } }

尺取法

把第三重循環去掉，重點在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';}